Pythonの高速フィボナッチ

こうです(lru_cacheをつかって)

from functools import lru_cache

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

こうです(自作キャッシュでメモ化して)

def fib(n):
    cache = {}
    def impl(ni):
        nonlocal cache
        if ni <= 1:
            return 1
        if ni not in cache:
            cache[ni] = impl(ni - 2) + impl(ni - 1)
        return cache[ni]
    return impl(n)

@shiracamusさんからのコメントを元に少し変更したもの↓

def fib(n, cache={0:1, 1:1}):
    if n not in cache:
        cache[n] = fib(n - 2) + fib(n - 1)
    return cache[n]

⚠️これは遅いです⚠️

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