人気ブログランキング | 話題のタグを見る

ループと再帰関数

関数型言語で一番戸惑うのはループを全て再帰関数で記述することだ。階乗の計算が再帰関数になるのは分かるが、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)
<< 末尾再帰 reduce と inject >>