「プログラマの数学」第６章再帰を見直す

前々から思っていたんですが、再帰についてよくわかってないので、結城浩著「プログラマの数学」の再帰の章を読み返すことにしました。

ハノイの塔の回答を出すプログラムは本に書かれているので飛ばすとして、今日は階乗を返す関数と、フィボナッチ数列を表示するスクリプトをPythonで作成してみました。

階乗を求める

N = int(input())
def kaijo1(i, ans):
   if i == 1:
       print(ans)
   else:
       ans *= i
       kaijo1(i-1, ans)

def kaijo2(i):
   if i == 1:
       return 1
   return i * kaijo2(i - 1)

kaijo1(N,1)
print(kaijo2(N))

Pythonの場合、標準ライブラリの「math」モジュールで「factorial」が提供されているので、階乗を求めるのは１行で済むんだけど、再帰を使って記述した場合は上記の様になります。回答を直接プリントさせるのが「kaijo1」、値を返すのが「kaijo2」で、明らかに後者の方がシンプルで良いですね。

フィボナッチ数列を表示する

本によると、フィボナッチ数列は

f(n) = f(n-1) + f(n-2)

で求められる様です。んで、書いたのが以下のコード

N = int(input())
def fibonacci(i):
   if i == 0:
       return 0
   elif i == 1:
       return 1
   else:
       return fibonacci(i-1) + fibonacci(i-2)
print([fibonacci(i) for i in range(N)])

めっちゃ遅い。

都度再帰で計算が発生するので、「100」」を与えると20分経っても結果は帰ってこなかったです。しかもPCのファンが全開で回り始めました。

そんなことあるかわからないですが、フィボナッチ数列をずらずら表示させたいのであれば以下の様な感じにした方がいいと思います。（再帰関係ないですが）

N = int(input())
fib_list = [0 for _ in range(N)]
fib_list[0] = 0
fib_list[1] = 1
for i in range(len(fib_list[2:])):
   fib_list[i + 2] = fib_list[i + 1] + fib_list[i]
print(fib_list)

感想

私はプログラマというわけでないですが、こういうの考えるのはパズル的で面白いと思った次第。