再帰の考え方

まず例を見てみよう。

for i in range(10):
  print i

上記の例では、iの状態を0から9まで変えながらループしている。ここで、1つのループをフレームと呼ぶことにする。次に再帰のコード例を見てみる。

def fib(n):
  if n==0 or n==1:
    return 1
  else:
    return fib(n - 1) + fib(n - 2)  # 過去のフレームの情報を取得!

さらにfor文を使用した例を見てみる。

def fib(n):
  num1, num2, tmp = 1, 1, 1
  for i in range(1, n):
    tmp = num1 + num2
    num1 = num2
    num2 = tmp
  return tmp

ここで、1つのフレームに対応して1つの状態が決まり、なおかつ同一フレーム内で別のフレームの情報も利用したいケースを考えよう。すると、再帰の例では、あるフレームにおいて別のフレームの情報を取得している。そして、for文の例では別のフレームに対応する状態を保存している。

さらに、リストデータを使用した場合を考えてみよう。あるフレームの状態はリストのあるインデックスに対する値に対応している。ここで、状態はリストとして保存されているので状態を保存ではなく参照できれば良いことに気が付く。

つまり、前述の先読みのテクニックとは、過去や未来のフレームの状態を現在のフレームで取得する方法ということになる。再帰の強みは過去や未来の状態を保存していなくてもいつでも取り出せることである。それに対して、for文を使用すると過去や未来の状態を保存したり参照したりする方法を管理しないといけない。その部分が再帰とfor文との本質的な違いではないかと思う。