再帰じゃないフィボナッチ数
フィボナッチ数列っていうのがあります。
再帰の実装サンプルなんかでよく使われるアレですが、普通に実装すると簡単に処理できなくなるアレです。
よくある実装はこんなかんじですよね。
def fib(n):
if n == 0 or n == 1:
return 1
return fib(n-1) + fib(n-2)
定義の通りに書いた感じです。これを手元のマシンで実行したところ、n=40ほどでもう帰ってこなくなりました。
では次に、メモ化による高速化を行うとどこまでいけるのでしょうか？
上記のサンプルでn=40で戻ってこなくなるのは、同じ計算が多すぎるからです。
なので特定のnに対するfib(n)の値を保存しておけば同じ計算を省くことができます。
memo = {}
def fib(n):
if n == 0 or n == 1:
return 1
if n in memo:
return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
これでn=40どころかn=500くらいまでは計算できるかと思いますが、n=1000となると、今度は再帰が深すぎることによるstack overflowが起きます。
末尾再帰最適化があればそれで実装するのもひとつの手ですが、そもそもフィボナッチ数列を実装するにあたり、再帰は必要なかったりします。
フィボナッチ数列は定義の通り、fib(n)はfib(n-1)とfib(n-2)のときの値のみから算出できます。言い換えると、fib(n-1)とfib(n-2)の時の値を何処かに保存しておけばfib(n)を計算できるはずです。
この考えに基づいた実装がこれです。
def fib(n):
a = 1
b = 1
for _ in xrange(n-1):
a,b = b,a+b
return b
aがfib(n-2)の値、bがfib(n-1)の値です。
それぞれ初期値fib(0)、fib(1)で初期化し、n=2以上からループに入ります。
ループの中ではaは計算前のbすなわちfib(n-1)の保存に使用し、bはa+bすなわちfib(n-1)+fib(n-2)の計算に使用します。
１ループが終了するとき、a=fib(n-1), b=fib(n)となっているので、次のループに対するnにってはa=fib(n-2), b=fib(n-1)となります。
これで反復のみの実装となったので、n=100000位はいけますかね。
