pythonの再帰運転が遅すぎる原因と解決策

今日pythonでフィボナッチ数列を作成しました.コードは以下の通りです.

def feb(i: int):
    if i == 0:
        return 1
    if i == 1:
        return 2
    return feb(i-2) + feb(i-1)
print(feb(73))

結果はそのまま実行しても結果が出ないので、73から27秒後に変更してみましたが、数値が大きすぎて実行時間が長すぎたようです・・・pythonは再帰を実行するたびに、前の数値を使うたびに、もう一度計算し直します・・・だからこんなに遅いのです.結果をキャッシュに格納すると、実行速度が向上します.

from functools import lru_cache
@lru_cache(maxsize=1024)
def feb(i: int):
    if i == 0:
        return 1
    if i == 1:
        return 2
    return feb(i-2) + feb(i-1)
print(feb(73))

これで73を運転しても秒で結果が出ます!