Ricorsione
Ultimo aggiornamento
La ricorsione è una funzione che chiama se stessa su una versione più piccola dello stesso problema, finché non arriva a un caso così piccolo da poter rispondere direttamente. Quel caso a risposta diretta è il caso base, e ogni funzione ricorsiva ne ha bisogno: fib(n) continua a dividersi in fib(n - 1) e fib(n - 2) finché non arriva a fib(1) o fib(0), che restituiscono semplicemente se stessi. La visualizzazione qui sopra esegue proprio questo: premi Play e guarda le chiamate ramificarsi in un albero, raggiungere i casi base sulle foglie e poi restituire i loro valori verso l'alto, combinandoli a ogni livello.
La seconda cosa che mostra l'animazione è lo stack delle chiamate: ogni chiamata iniziata ma non ancora terminata. Lo stack cresce man mano che le chiamate scendono, raggiunge il picco alla profondità della ricorsione e si svuota quando tornano i risultati, ed è per questo che una ricorsione profonda può causare uno stack overflow, mentre un ciclo iterativo non fa mai crescere lo stack. La stessa forma delle chiamate guida la visita in profondità, il merge sort e la maggior parte delle operazioni su un albero binario.
Complessità temporale e spaziale
Per il Fibonacci ricorsivo ingenuo mostrato sopra e per le due soluzioni standard:
| Approccio | Tempo | Spazio | Note |
|---|---|---|---|
| Ricorsione ingenua | O(2^n) | O(n) | L'albero delle chiamate raddoppia a ogni livello; lo spazio è lo stack più profondo, non l'intero albero. |
| Con memoizzazione | O(n) | O(n) | Ogni fib(k) viene calcolato una volta e salvato in cache; i sottoalberi ripetuti diventano semplici letture. |
| Ciclo iterativo | O(n) | O(1) | Due variabili che scorrono sostituiscono del tutto lo stack. |
| Qualsiasi ricorsione, in generale | chiamate × lavoro per chiamata | O(max depth) | Lo stack contiene un frame per ogni chiamata iniziata ma non ancora terminata. |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | La prima chiamata fib(n) va sullo stack delle chiamate. |
| 2 | Le serve fib(n - 1), quindi anche quella chiamata va sullo stack; il genitore aspetta. |
| 3 | Le chiamate continuano ad annidarsi finché una non riguarda n <= 1: il caso base risponde subito, senza chiamate più profonde. |
| 4 | Il valore del caso base torna al genitore, che ora può avviare la sua seconda chiamata, fib(n - 2). |
| 5 | Quando entrambi i figli hanno restituito, il genitore li somma e restituisce a sua volta; il suo frame lascia lo stack. |
| 6 | Il ritorno si ripete risalendo l'albero finché il frame della prima chiamata non viene tolto con la risposta finale e lo stack è vuoto. |
Esempio svolto
Valutazione di fib(4) nell'ordine esatto delle chiamate, come la riproduce l'animazione:
| Chiamata | Stack in quel momento | Restituisce |
|---|---|---|
fib(4) | fib(4) | aspetta i figli |
fib(3) | fib(4) > fib(3) | aspetta i figli |
fib(2) | fib(4) > fib(3) > fib(2) | aspetta i figli |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (caso base) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (caso base) |
fib(2) combina | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (caso base) |
fib(3) combina | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) di nuovo | fib(4) > fib(2) | 1, ricalcolato da zero |
fib(4) combina | fib(4) | 2 + 1 = 3 |
Quando usare la ricorsione
| Usala quando | Evitala quando |
|---|---|
| Il problema è autosimile: alberi, strutture annidate, divide et impera | Un semplice ciclo esprime la stessa cosa senza frame sullo stack |
La profondità è limitata e contenuta, come O(log n) nel merge sort | Su input enormi la profondità può arrivare alla dimensione dell'input, con il rischio di uno stack overflow |
| Il backtracking ha bisogno dello stack per ricordare da dove riprendere | Gli stessi sottoproblemi si ripetono e non li stai salvando in cache |
| La versione ricorsiva è chiaramente più facile da leggere e verificare | Sei in un ciclo critico in cui il costo delle chiamate conta in modo misurabile |
Codice Recursion
Un'implementazione di Recursion pulita ed eseguibile in Python, JavaScript, Java, C++, C. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Recursion in Python
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Codice Recursion in JavaScript
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Codice Recursion in Java
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Codice Recursion in C++
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Codice Recursion in C
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Domande frequenti sulla ricorsione
Cos'è il caso base nella ricorsione?
L'input abbastanza piccolo da poter rispondere senza un'altra chiamata ricorsiva. Per
fib(n) è n <= 1, che restituisce direttamente n. Senza un caso base raggiungibile le chiamate non si fermano mai, lo stack continua a crescere e il programma va in crash con uno stack overflow.Cos'è lo stack delle chiamate e perché conta?
Il runtime tiene un frame per ogni chiamata iniziata ma non ancora terminata, con i suoi argomenti e le sue variabili locali. La profondità della ricorsione è uguale all'altezza dello stack, quindi una ricorsione profonda
n livelli usa O(n) di memoria anche se ogni chiamata fa pochissimo lavoro. La fila di etichette sotto l'animazione mostra proprio questo stack che cresce e si svuota.Perché il Fibonacci ricorsivo richiede tempo esponenziale?
Perché gli stessi sottoproblemi vengono ricalcolati più e più volte: nell'esempio svolto qui sopra,
fib(2) viene valutato due volte dentro fib(4), e la duplicazione raddoppia più o meno a ogni livello, per un totale di O(2^n) chiamate. Salvare in cache ogni risultato la prima volta che viene calcolato, la cosiddetta memoizzazione, riduce l'albero a O(n).La ricorsione è meglio dell'iterazione?
Nessuna delle due è sempre migliore. Ogni ricorsione si può riscrivere come un ciclo con uno stack esplicito, e ogni ciclo come una ricorsione. La ricorsione vince in leggibilità sui problemi autosimili come la visita di un albero e la visita in profondità; l'iterazione vince su memoria e costo delle chiamate nelle scansioni lineari.
Cosa causa uno stack overflow in una funzione ricorsiva?
O un caso base mancante o irraggiungibile, per cui le chiamate non si fermano mai, oppure una ricorsione corretta la cui profondità è semplicemente troppo grande per il limite dello stack del runtime, come una chiamata ricorsiva per ogni elemento su un input di milioni di elementi. Le soluzioni sono garantire il caso base, limitare la profondità o passare all'iterazione.
Quali algoritmi sono naturalmente ricorsivi?
Gli ordinamenti divide et impera come il merge sort e il quicksort, le visite di un albero binario e dei grafi, la ricerca binaria, i rompicapi con backtracking come le N regine e tutto ciò che è definito su strutture annidate, come un JSON o un file system.
Risorse correlate
Altre visualizzazioni
