Pythonで再帰を使ってフィボナッチ数に挑戦してみた

フィボナッチを再帰で解く方法を教えてもらったので、早速書いてみる。

フィボナッチ数 – Wikipedia

コード

#!/usr/bin/python
# -*- coding: utf-8 -*-
s0 = 0
s1 = 0
s2 = 0

def f1(x):
    global s0
    s0 += 1
    if x < 1: return 0
    elif x < 3: return 1
    return f1(x-1) + f1(x-2)

def f2(x,y,z):
    global s1
    s1 += 1
    if 1 > z: return x
    return f2(y,x+y,z-1)
    def f3(x,y,z):
    global s2
    s2 += 1
    for i in xrange(z):
    t = x + y
    x = y
    y = t
    return x

if __name__ == "__main__":
    count = 20
    print 'count:',count
    for i in xrange(count):
        print f1(i),
        print '\nCall:',s0
    for i in xrange(count):
        print f2(0,1,i),
        print '\nCall:',s1
    for i in xrange(count):
        print f3(0,1,i),
        print '\nCall:',s2

1. f1()は、漸化式を教えてもたらって書いたやつ。
2. f2()は、漸化式を知らなかった時に書いてたやつ。
3. f3()は、再帰を使わずに書いてみたが、スピードはこれが最速。
4. s0,s1,s2 は関数の呼び出し回数を知るために使っている。

実行結果

% ./Fibonacci.py
count: 20
 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Call: 21872
 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Call: 210
 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
Call: 20

感想

1. フィボナッチを、というか漸化式を知らなかったが、ナカナカ面白い。
2. 問題を解決するときに再帰を使用する場合、注意して使用しなければあっと言う間にリソースを食いつぶしてしまいそう。
3. 再帰を GAE などのクラウド環境を利用するときには注意が必要な感じ。
4. ウィキペディアに書いてあったトリボナッチ数、テトラナッチ数にも挑戦してみると面白そう。
5. あとは、lambda を使って解いてみるとか。
6. 数学ガール読んでみようかしら。

もっと美しいコードを目指して精進したい。

関連記事