Fibonacci

斐波那契数列

≈ 20 min · python-recursion · Open in WolfCode

Two recursive calls per non-base call. The call tree explodes — but the code reads like the math.

Python · runnable

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

for x in range(11):
    print(f"fib({x:>2}) = {fibonacci(x)}")

Loading Python runtime (~5 MB, one-time)…

Why it's slow

Each call makes two recursive calls. The call tree for fib(5) evaluates fib(3) twice and fib(1) five times. For n = 30 the function makes over a million calls; for n = 50, billions.

The iterative version — linear time

def fibonacci_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fibonacci_iter(30))     # 832040 — instant
print(fibonacci_iter(50))     # 12586269025 — also instant

Loading Python runtime (~5 MB, one-time)…