mastorna.it
EN

Algoritmi · Tecniche di progettazione

Ricorsione e stack delle chiamate

La ricorsione trasforma un problema in copie più piccole dello stesso problema. Il codice può essere breve; l’esecuzione, però, costruisce una struttura concreta di chiamate, variabili locali e risultati sospesi.

Pensare ricorsivamente

Per risolvere un’istanza non serve immaginare tutte le chiamate insieme. Si assume che la funzione sappia già risolvere un’istanza più piccola, poi si usa quel risultato per costruire la soluzione corrente.

1

Caso base

Un’istanza risolvibile direttamente, senza altre chiamate.

2

Passo ricorsivo

Riduce il problema e combina il risultato restituito.

3

Progresso

Ogni chiamata deve avvicinarsi davvero al caso base.

Due direzioni. Nella discesa si creano le chiamate; nella risalita si restituiscono e combinano i risultati. Confonderle è una delle principali difficoltà iniziali.

Perché una ricorsione termina ed è corretta

  1. Il caso base è corretto. Per esempio 0! = 1 e 1! = 1.
  2. La misura diminuisce. In fact(n) il parametro passa da n a n−1 ed è limitato inferiormente.
  3. Il passo conserva la correttezza. Se fact(n−1) è corretto, moltiplicarlo per n produce n!.

Questo ragionamento è vicino all’induzione matematica: caso base, ipotesi su un problema più piccolo e passo induttivo.

Che cosa contiene lo stack delle chiamate

Ogni chiamata sospesa occupa un frame. Il frame conserva parametri, variabili locali, punto in cui riprendere e spazio per il valore restituito. Lo stack segue la regola LIFO: l’ultima chiamata entrata è la prima a terminare.

Cima dello stackfact(2)n = 2 · attende fact(1)
fact(3)n = 3 · attende fact(2)
fact(4)n = 4 · attende fact(3)

La chiamata più recente è in alto ↑

Stack overflow. Lo stack ha dimensione finita. Una ricorsione senza progresso, o semplicemente troppo profonda, esaurisce i frame disponibili.

Laboratorio: segui ogni chiamata

Scegli un esempio e avanza un’operazione alla volta. L’albero mostra tutte le chiamate; lo stack mostra soltanto la catena attiva in quell’istante.

Tutte le chiamate

Albero di esecuzione

scorri se necessario
Solo chiamate attive

Call stack

Chiamate
0
Profondità massima
0
Frame attivi
0
Cache hit
0
  1. fact(n)
  2. if n ≤ 1
  3. return 1
  4. return n · fact(n − 1)
operazione corrente chiamata sospesa risultato restituito cache hit

Fattoriale: una sola catena di chiamate

Definizione

0! = 1
n! = n · (n−1)! per n > 0

Tempo

T(n) = T(n−1) + Θ(1) = Θ(n). Una chiamata per ogni valore da n a 1.

Spazio

Θ(n) frame simultanei prima che inizi la risalita.

Per fact(5), la discesa costruisce 5 · fact(4), poi 4 · fact(3) e così via. Solo raggiunto il caso base iniziano le moltiplicazioni: 1, 2, 6, 24, 120.

Fibonacci: un albero con lavoro ripetuto

Definizione

F₀ = 0, F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂

Tempo ingenuo

T(n) = T(n−1) + T(n−2) + Θ(1) = Θ(φⁿ), dove φ ≈ 1,618.

Spazio ingenuo

Θ(n): l’albero è grande, ma nello stack vive un solo cammino alla volta.

Albero ≠ stack. L’albero misura tutte le chiamate eseguite; lo stack misura la profondità delle chiamate ancora aperte. Per fib(n) le chiamate totali sono 2Fₙ₊₁−1, ma la profondità è soltanto Θ(n).

Memoization: ricordare invece di ricalcolare

Fibonacci ricalcola molte volte fib(3), fib(2) e gli stessi casi base. Una cache indicizzata da n trasforma ogni sottoproblema dopo il primo in un accesso costante. Attiva “Usa memoization” nel laboratorio: i nodi viola terminano leggendo un risultato già noto.

Ricorsione ingenuaΘ(φⁿ)

tempo · Θ(n) stack

Con memoizationΘ(n)

tempo · Θ(n) stack + cache

Iterativo ottimizzatoΘ(n)

tempo · Θ(1) spazio

Quando usare ricorsione e quando iterazione

Preferisci ricorsionePreferisci iterazione
La struttura è naturalmente ricorsiva: alberi, directory, divide et impera, backtracking.La profondità può essere molto grande o dipende da input non fidati.
Il codice rispecchia direttamente una definizione e resta più verificabile.Esiste uno stato compatto e ripetitivo, come due soli valori consecutivi di Fibonacci.
La profondità è logaritmica o comunque controllata.Overhead delle chiamate e memoria dello stack sono rilevanti.

La tail recursion non risolve automaticamente il problema: JavaScript e PHP non garantiscono in generale l’eliminazione del frame ricorsivo. Se la profondità può essere elevata, usa un ciclo o uno stack esplicito.

Errori comuni

  • Caso base assente o irraggiungibile: le chiamate continuano fino allo stack overflow.
  • Nessun progresso: f(n) richiama f(n) o allontana n dal caso base.
  • Confondere valore restituito ed effetto: stampare un risultato non equivale a restituirlo alla chiamata precedente.
  • Ignorare sottoproblemi ripetuti: Fibonacci ingenuo sembra breve ma genera un numero esponenziale di chiamate.
  • Dimenticare lo stack nell’analisi dello spazio: una funzione senza array ausiliari non è necessariamente Θ(1) in memoria.