all Python 3Algorithms & data structuresterm

Fibonacci numbers

math

F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2). Iteratively O(n), recursively O(2^n), with lru_cache O(n).

Syntax

def fib(n): ...

Naive recursion recomputes the same values again and again: fib(35) takes seconds and fib(50) is hopeless, while a single @lru_cache(maxsize=None) on the function removes the problem. Recursion has a second ceiling as well — roughly a thousand nested calls before RecursionError — so large n calls for a loop rather than memoisation. Binet's float formula starts producing wrong digits around n=71, whereas an integer loop stays exact for any n because Python integers never overflow.

Examples

# Итеративно — O(n)
def fib_iter(n):
    if n <= 1: return n
    a, b = 0, 1
    for _ in range(2, n+1):
        a, b = b, a+b
    return b
print([fib_iter(i) for i in range(10)])  # → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

# Рекурсивно — O(2^n) (медленно!)
def fib_rec(n):
    if n <= 1: return n
    return fib_rec(n-1) + fib_rec(n-2)
print(fib_rec(10))  # → 55 (для малых n)

# С lru_cache — O(n) + мемоизация
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1: return n
    return fib_memo(n-1) + fib_memo(n-2)
print(fib_memo(50))  # → 12586269025

# Генератор Фибоначчи
from itertools import islice
def fib_gen():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b
print(list(islice(fib_gen(), 10)))  # → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
# Матричный метод O(log n)
def mat_mul(A, B):
    return [
        [A[0][0]*B[0][0]+A[0][1]*B[1][0], A[0][0]*B[0][1]+A[0][1]*B[1][1]],
        [A[1][0]*B[0][0]+A[1][1]*B[1][0], A[1][0]*B[0][1]+A[1][1]*B[1][1]],
    ]
def mat_pow(M, n):
    if n == 1: return M
    if n % 2 == 0:
        half = mat_pow(M, n//2)
        return mat_mul(half, half)
    return mat_mul(M, mat_pow(M, n-1))
def fib_matrix(n):
    if n == 0: return 0
    return mat_pow([[1, 1], [1, 0]], n)[0][1]
print(fib_matrix(10))  # → 55

# Числа Фибоначчи, не превышающие N
def fib_until(n):
    a, b = 0, 1
    result = []
    while a <= n:
        result.append(a)
        a, b = b, a+b
    return result
print(fib_until(100))  # → [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]

Fibonacci numbers

Syntax

Examples

See also