フィボナッチ数/Python

提供: MonoBook
移動: 案内検索

Pythonフィボナッチ数(fibonacci)の記述例。

記述例1[編集]

PythonではPython 2.4から導入されたデコレーターを用いてメタプログラミングを実現した人がおり[1]、それを使えば関数[email protected]_recursive」と書くことで末尾再帰最適化を明示することができる。 なお、同じくものをクラスではなくクロージャーで書き直した人もいる[2]

これらを用いた記述例は以下のようになる。末尾呼び出し最適化[email protected]_recursive 」の記述を消せばよい。その場合はエントリポイント内のループ変数「x」が大きいとスタックオーバーフローを起こすと思う。

def fib(n):
    @tail_recursive
    def fib_iter(a, b, m):
        return a if m == 0 else fib_iter(b, a + b, m - 1)
    return fib_iter(0, 1, n)
 
if __name__ == "__main__":
    for x in range(1, 100):
        print fib(x),

関連項目[編集]

参考文献[編集]

  1. http://d.hatena.ne.jp/wasabiz/20110118/1295335821
  2. http://d.hatena.ne.jp/tanihito/20110119/1295459297

外部リンク[編集]