関数型言語で一番戸惑うのはループを全て再帰関数で記述することだ。階乗の計算が再帰関数になるのは分かるが、1から10までの整数を足すような次のようなループまで再帰関数で書くのは一見無理なような気がする。
total = 0 for i in 1..10 total += i end puts total しかし、全てのプログラムは関数である考えると、上の手続き型プログラムも再帰関数で記述することができる。つまり、まず整数 i から j までを加算する関数 sum(i, j) を考えるのだ。1から10までの加算は sum(1, 10) だ。ところが、これは 1 と 2から10までを加算したものの和と等しいので、sum(1, 10) = 1 + sum(2, 10) である。この考え方を次のように繰り返していくと、sum(1, 10) は次のように展開できる。 sum(1, 10) = 1 + sum(2, 10) = 1 + (2 + sum(2, 10)) = 1 + (2 + (3 + sum(4, 10))) ... = 1 + (2 + (... (9 + sum(10,10))...) ここで、sum(10, 10) = 10 は明らかだ。 つまり、上の式の展開は次のような置き換えを次々に繰り返していることになる。 sum(i, j) = j ( i = j のとき ) i + sum(i + 1, j) ( それ以外 ) この漸化式は次のようにプログラムすることもできる。 def sum(i, j) if i == j j else i + sum(i + 1, j) end end そうして、sum(1, 10) を実行してみると、1から10までの総和である55が戻値になる。ループを再帰関数で表現するためには、最初に関数を考えてそれを展開してみると目的の再帰関数を思いつきやすい。また、上のコーディングは、次のように書くと再帰関数をそのまま記述するため簡潔になる。 def sum(i, j) i == j ? j : i + sum(i + 1, j) end 上のコードには、変数 total に i を足して total に再代入するなどという手続きの工夫は全く記述されていない。ただ、関数 sum(i, j) の再帰的定義をそのまま記述してあるだけだ。このようなものでも、sum(1, 10) のように引数を渡すと、ちゃんと答を返してくるのが不思議だ。
by tnomura9
| 2008-02-04 06:18
| Ruby
|
Comments(0)
|
カテゴリ
新型コロナウイルス 主インデックス Haskell 記事リスト 圏論記事リスト 考えるということのリスト 考えるということ ラッセルのパラドックス Haskell Prelude Ocaml ボーカロイド 圏論 jQuery デモ HTML Python ツールボックス XAMPP Ruby ubuntu WordPress 脳の話 話のネタ リンク 幸福論 キリスト教 心の話 メモ 電子カルテ Dojo JavaScript C# NetWalker ed と sed HTML Raspberry Pi C 言語 命題論理 以前の記事
最新のトラックバック
最新のコメント
ファン
記事ランキング
ブログジャンル
画像一覧
|
ファン申請 |
||