フィボナッチ数/Python
< フィボナッチ数
ナビゲーションに移動
検索に移動
Pythonのフィボナッチ数(fibonacci)の記述例。
記述例1[編集 | ソースを編集]
PythonではPython 2.4から導入されたデコレーターを用いてメタプログラミングを実現した人がおり[1]、それを使えば関数の頭に「@tail_recursive」と書くことで末尾再帰最適化を明示することができる。 なお、同じくものをクラスではなくクロージャーで書き直した人もいる[2]。
これらを用いた記述例は以下のようになる。末尾呼び出し最適化を用いない場合には「@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),