Molte quantità si descrivono più facilmente in funzione dei valori precedenti che con una formula diretta: il numero di mosse per risolvere un rompicapo, il tempo di esecuzione di un algoritmo ricorsivo, il saldo di un conto con interessi. Una relazione di ricorrenza esprime proprio questo legame. Risolverla significa trovare una forma chiusa, cioè una formula che dia direttamente l'n-esimo valore senza calcolare tutti quelli prima.
Definizione
Una relazione di ricorrenza per una successione a₀, a₁, a₂, … è un'equazione che esprime aₙ in funzione di alcuni termini precedenti, insieme a una o più condizioni iniziali.
Esempi:
- aₙ = aₙ₋₁ + 3, con a₀ = 2: successione aritmetica 2, 5, 8, 11, …
- aₙ = 2aₙ₋₁, con a₀ = 1: potenze di 2.
- Fₙ = Fₙ₋₁ + Fₙ₋₂, con F₀ = 0 e F₁ = 1: i numeri di Fibonacci.
Senza condizioni iniziali la ricorrenza non individua una successione unica: aₙ = 2aₙ₋₁ è soddisfatta sia da 1, 2, 4, … sia da 3, 6, 12, …
Metodo 1: sostituzione iterata
Si sostituisce la ricorrenza dentro sé stessa finché non emerge uno schema, poi lo si verifica per induzione.
La torre di Hanoi
Per spostare n dischi dal primo al terzo piolo bisogna spostare i primi n − 1 sul piolo di appoggio, spostare il disco più grande, e poi riportare gli n − 1 sopra di esso. Il numero minimo di mosse soddisfa:
Hₙ = 2Hₙ₋₁ + 1, con H₁ = 1
Sostituendo:
Hₙ = 2(2Hₙ₋₂ + 1) + 1 = 4Hₙ₋₂ + 2 + 1 = 8Hₙ₋₃ + 4 + 2 + 1 = …
Dopo n − 1 passaggi: Hₙ = 2ⁿ⁻¹H₁ + 2ⁿ⁻² + … + 2 + 1 = 2ⁿ⁻¹ + … + 1 = 2ⁿ − 1.
Con 10 dischi servono 1023 mosse; con 64 dischi, il numero è circa 1,8 · 10¹⁹. La forma chiusa rende evidente una crescita che la ricorrenza nasconde.
Metodo 2: equazione caratteristica
Per le ricorrenze lineari omogenee a coefficienti costanti di secondo ordine, del tipo
aₙ = c₁aₙ₋₁ + c₂aₙ₋₂
si cerca una soluzione della forma aₙ = rⁿ. Sostituendo e dividendo per rⁿ⁻² si ottiene l'equazione caratteristica:
r² − c₁r − c₂ = 0
- Se ha due radici distinte r₁ e r₂, la soluzione generale è aₙ = α r₁ⁿ + β r₂ⁿ.
- Se ha una radice doppia r, la soluzione generale è aₙ = (α + βn) rⁿ.
Le costanti α e β si ricavano dalle condizioni iniziali.
Esempio svolto
aₙ = 5aₙ₋₁ − 6aₙ₋₂, con a₀ = 1 e a₁ = 4.
Equazione caratteristica: r² − 5r + 6 = 0, radici 2 e 3. Quindi aₙ = α · 2ⁿ + β · 3ⁿ.
- n = 0: α + β = 1
- n = 1: 2α + 3β = 4
Risolvendo: β = 2, α = −1. Forma chiusa: aₙ = 2 · 3ⁿ − 2ⁿ. Verifica: a₂ = 18 − 4 = 14, e dalla ricorrenza 5 · 4 − 6 · 1 = 14.
Fibonacci
Per Fₙ = Fₙ₋₁ + Fₙ₋₂ l'equazione è r² − r − 1 = 0, con radici φ = (1 + √5)/2 ≈ 1,618 e ψ = (1 − √5)/2 ≈ −0,618. Imponendo F₀ = 0 e F₁ = 1 si ottiene la formula di Binet:
Fₙ = (φⁿ − ψⁿ) / √5
Poiché |ψ| < 1, il termine ψⁿ diventa trascurabile e Fₙ è l'intero più vicino a φⁿ/√5. I numeri di Fibonacci crescono quindi in modo esponenziale, con base circa 1,618.
Ricorrenze e algoritmi
Il tempo di esecuzione di un algoritmo ricorsivo soddisfa naturalmente una ricorrenza. Due esempi istruttivi.
Fibonacci ricorsivo ingenuo
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
Il numero di chiamate T(n) soddisfa T(n) = T(n − 1) + T(n − 2) + 1, che cresce come Fₙ, cioè esponenzialmente. Memorizzando i risultati già calcolati, o iterando dal basso, il costo diventa lineare.
Divide et impera
Un algoritmo che divide il problema in due metà, le risolve ricorsivamente e combina i risultati in tempo lineare soddisfa T(n) = 2T(n/2) + cn. Iterando, a ogni livello di ricorsione il lavoro totale è cn, e i livelli sono circa log₂ n. Il totale è dell'ordine di n log n: è il caso del merge sort. Questo schema generale è codificato nel cosiddetto teorema dell'esperto (master theorem), che dà la soluzione per le ricorrenze della forma T(n) = aT(n/b) + f(n).
Un controllo pratico
Quando si trova una forma chiusa conviene sempre verificarla numericamente sui primi valori:
def ricorrenza(n):
a = [1, 4]
for k in range(2, n + 1):
a.append(5 * a[-1] - 6 * a[-2])
return a[n]
assert all(ricorrenza(n) == 2 * 3**n - 2**n for n in range(20))
Il controllo non sostituisce la dimostrazione, ma intercetta subito gli errori di calcolo nelle costanti.
In sintesi
- Una ricorrenza definisce ogni termine tramite i precedenti e richiede condizioni iniziali.
- La sostituzione iterata fa emergere lo schema, da confermare per induzione.
- Le ricorrenze lineari omogenee si risolvono con l'equazione caratteristica.
- Fibonacci cresce come φⁿ; la torre di Hanoi richiede 2ⁿ − 1 mosse.
- Il costo degli algoritmi ricorsivi è una ricorrenza: divide et impera porta spesso a n log n.
