Recorrências

Uma recorrência define uma sequência em termos dos termos anteriores. Toda função recursiva gera uma recorrência para o seu custo, e resolvê-la dá a complexidade.

Fibonacci

F(0) = 0,  F(1) = 1,  F(n) = F(n−1) + F(n−2)

Recorrências lineares homogêneas se resolvem pela equação característica. Aqui ela é x² = x + 1, com raízes φ = (1+√5)/2 ≈ 1,618 e ψ = (1−√5)/2. Daí sai a fórmula de Binet:

F(n) = (φⁿ − ψⁿ) / √5

A versão recursiva ingênua faz cerca de φⁿ chamadas, ou seja, crescimento exponencial. Com memoização passa a ser O(n). Com exponenciação de matrizes, O(log n).

from functools import cache

@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

def fib_matriz(n):
    # [[1,1],[1,0]]^n = [[F(n+1), F(n)], [F(n), F(n-1)]]
    def 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]]]
    r, m = [[1, 0], [0, 1]], [[1, 1], [1, 0]]
    while n:
        if n & 1:
            r = mul(r, m)
        m = mul(m, m)
        n >>= 1
    return r[0][1]