Python3.2 or higher lru_cacheで再帰をキャッシュ

fibonacci_lrucache.py

# -*- coding: utf-8 -*-

#
# フィボナッチ数列 第30項を計算する関数に
# lru_cacheを使って関数の呼び出し回数を比較
#

from functools import lru_cache

exec_counter = 0

@lru_cache(maxsize=None)

def fibonacci(n):
    global exec_counter

    exec_counter += 1
    if n == 0:
        return 0
    if n == 1:
        return 1
    
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(30))
print(f"exec_count : {exec_counter}")

# キャッシュなし
# 832040
# exec_count: 2692537

# キャッシュあり
# 832040
# exec_count: 31