フィボナッチ数/Python

Pythonのフィボナッチ数（fibonacci）の記述例。

記述例1

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

これらを用いた記述例は以下のようになる。末尾呼び出し最適化を用いない場合には「@tail_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),

関連項目

• Python