Pythonでn番目のフィボナッチ数を求める

フィボナッチ数列は 0, 1, 1, 2, 3, 5, 8, 13, ... と続く数列です。

このn番目の値をPythonで求めるには以下のようなにすれば良いです。

単純な方法

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

キャッシュを使う方法

標準モジュールのlru_cacheデコレータをつけるだけです。

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    else:
        return fib(n - 2) + fib(n - 1)

比較

fib(40) の場合の比較です。キャッシュを使う方が圧倒的に高速です。

	呼び出し回数	処理時間
単純な方法	331160281	52.9 sec
キャッシュを使う方法	41	0.00018 sec