 |
La ricorsione è una tecnica fondamentale in programmazione, in cui una funzione chiama sé stessa per risolvere un problema. È un metodo elegante per affrontare problemi complessi, ma va usato con attenzione: se non progettata correttamente, può causare errori o inefficienze.
Come funziona la ricorsione?
Una funzione ricorsiva è composta da due elementi essenziali:
- Il caso base (base case): la condizione che ferma la ricorsione.
- La chiamata ricorsiva (recursive case): la funzione si richiama su una versione semplificata del problema.
Esempio: Calcolo del fattoriale
function factorial(n) {
if (n === 0) {
return 1; // base case
}
return n * factorial(n - 1); // recursive call
}Nel codice:
- Se
nè 0, la funzione ritorna 1 → caso base. - Altrimenti, moltiplica
nperfactorial(n - 1)→ chiamata ricorsiva.
Esecuzione passo-passo
factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * (1 * factorial(0)))
= 3 * 2 * 1 * 1
= 6Il cuore della ricorsione: caso base + semplificazione
Una funzione ricorsiva deve sempre:
- Avere un caso base, che fermi le chiamate ricorsive.
- Semplificare il problema a ogni passo, per avvicinarsi al caso base.
Senza caso base, la funzione continua a chiamarsi all'infinito, causando un stack overflow.
Altro esempio: Countdown
function countdown(n) {
if (n <= 0) {
console.log("Done!");
return; // base case
}
console.log(n);
countdown(n - 1); // recursive call
}In questo esempio:
- Il caso base è
n <= 0 - Ogni chiamata ricorsiva riduce
ndi 1 - Prima o poi,
nraggiunge 0 → la ricorsione termina
Quando usare la ricorsione?
La ricorsione è adatta quando il problema:
- Può essere suddiviso in sottoproblemi simili
- Ha una struttura ricorsiva naturale (es. alberi, strutture annidate)
- Richiede algoritmi divide-et-impera (es. mergesort, quicksort)
Esempio: visita di un albero
const tree = {
value: 1,
children: [
{ value: 2, children: [] },
{
value: 3,
children: [
{ value: 4, children: [] },
{ value: 5, children: [] }
]
}
]
};
function printTree(node) {
console.log(node.value);
for (let child of node.children) {
printTree(child); // recursive call
}
}Qui la ricorsione permette di attraversare ogni nodo dell’albero, visitando ogni sottostruttura con la stessa logica.
Attenzione: non abusarne
Usare la ricorsione in modo scorretto può causare:
- Stack overflow (troppe chiamate annidate)
- Prestazioni peggiori rispetto a un ciclo iterativo
- Codice meno leggibile o più difficile da mantenere
Esempio di ricorsione inefficiente: Fibonacci
function fibonacci(n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}Questo approccio ha complessità esponenziale, perché calcola gli stessi valori più volte. Una soluzione iterativa o con memoizzazione è più adatta.
Linee guida per usare bene la ricorsione
✅ Usa la ricorsione quando:
- Il problema è naturalmente ricorsivo
- Esiste un caso base chiaro
- Ogni passo riduce la complessità del problema
🚫 Evita la ricorsione quando:
- Una versione iterativa è più semplice o più efficiente
- Non hai piena padronanza del flusso di esecuzione ricorsiva
- Il problema richiede troppe chiamate profonde (oltre il limite dello stack)
Conclusione
La ricorsione è uno strumento potente, ma non è una scorciatoia. È elegante, compatta e a volte necessaria — ma va usata con consapevolezza.
Come ogni tecnica avanzata, la ricorsione dà il meglio solo nelle mani di chi la padroneggia.
Per chi è alle prime armi, può essere più sicuro iniziare con approcci iterativi, e passare alla ricorsione quando si ha piena comprensione del caso base, dello stack di chiamate, e delle implicazioni prestazionali.
Follow me #techelopment
Official site: www.techelopment.it
facebook: Techelopment
instagram: @techelopment
X: techelopment
Bluesky: @techelopment
telegram: @techelopment_channel
whatsapp: Techelopment
youtube: @techelopment
