Introduzione
La ricorsione è un concetto potente della programmazione: una funzione che chiama se stessa.
All'inizio può essere un po' difficile da afferrare, ma una volta che ne capisci i fondamenti diventa uno strumento prezioso per risolvere problemi complessi.
In questo tutorial esploreremo la ricorsione in JavaScript con esempi facili da capire.
Che cos'è la ricorsione?
La ricorsione si ha quando una funzione chiama se stessa, in modo diretto o indiretto.
È simile a un ciclo, ma consiste nel suddividere un problema in sotto-problemi più piccoli e più gestibili.
Esempio 1: conto alla rovescia
Iniziamo con un esempio semplice: una funzione di conto alla rovescia.
function countdown(num) {
// Base case
if (num <= 0) {
console.log('Blastoff!');
return;
}
// Recursive case
console.log(num);
countdown(num - 1);
}
// Call the function
countdown(5);
In questo esempio:
-
Caso base: quando
num diventa minore o uguale a 0, la funzione stampa "Blastoff!" e smette di chiamare se stessa.
-
Caso ricorsivo: la funzione stampa il valore corrente di
num e chiama se stessa con num - 1.
Esempio 2: il fattoriale
Ora vediamo un esempio classico di ricorsione: il calcolo del fattoriale di un numero.
function factorial(n) {
// Base case
if (n === 0 || n === 1) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
// Test the function
console.log(factorial(5)); // Output: 120
In questo esempio:
-
Caso base: quando
n è 0 o 1, la funzione restituisce 1.
-
Caso ricorsivo: la funzione moltiplica
n per il fattoriale di n - 1.
Concetti chiave
Il caso base
Ogni funzione ricorsiva deve avere almeno un caso base, una condizione in cui la funzione smette di chiamare se stessa.
Senza un caso base, la ricorsione continuerebbe all'infinito, causando uno stack overflow.
Il caso ricorsivo
Il caso ricorsivo definisce come la funzione chiama se stessa con una versione più piccola o più semplice del problema.
Vantaggi e svantaggi della ricorsione
Vantaggi:
- Una soluzione elegante per certi problemi.
- Riprende il concetto di induzione matematica.
Svantaggi:
- Può essere meno efficiente di una soluzione iterativa.
- Può portare a uno stack overflow nelle ricorsioni profonde.
Conclusione
La ricorsione è una tecnica preziosa: può semplificare problemi complessi suddividendoli in sotto-problemi più piccoli e più gestibili.
Capire i casi base e i casi ricorsivi è fondamentale per scrivere soluzioni ricorsive efficaci in JavaScript.
Per saperne di più:
Istruzioni
Gestisci una pizzeria e offri tre tipi di pizza:
- Margherita: $7
- Caprese: $9
- Formaggio: $10
Se i clienti lo desiderano, possono aggiungere un numero illimitato di opzioni extra: "ExtraSauce" per $1 oppure "ExtraToppings" per $2.
Il tuo compito è scrivere del codice che aiuti il cliente a capire quanto spenderà.
Calcola il prezzo di una pizza
Ricevendo il nome della pizza come primo argomento e un numero illimitato di opzioni extra, calcola il prezzo della pizza in dollari.
pizzaPrice('Margherita');
// => 7
pizzaPrice('Caprese', 'ExtraSauce', 'ExtraToppings');
// => 12
pizzaPrice(
'Caprese',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
'ExtraToppings',
);
// => 17
Calcola il prezzo totale di un ordine
La funzione viene chiamata con un array di PizzaOrder e deve restituire il prezzo totale dell'ordine in dollari.
Ogni PizzaOrder ha una proprietà pizza, il nome della pizza, e una proprietà extras, l'array delle opzioni extra.
const margherita = new PizzaOrder('Margherita');
const caprese = new PizzaOrder('Caprese', 'ExtraToppings');
orderPrice([margherita, caprese]);
// => 18
Ti accorgerai che non puoi scrivere questa funzione usando la ricorsione: un test con una quantità enorme di ordini farà scattare un Maximum call stack size exceeded.
Non preoccuparti, è intenzionale: prova a implementare questa funzione con un ciclo imperativo!
Hai molte opzioni: puoi usare, tra le altre cose, reduce o un ciclo for.
Quando l'interprete JavaScript esegue il codice JavaScript, tiene traccia delle funzioni in cui è entrato (che ha iniziato a chiamare) su una struttura dati chiamata «stack».
Quando la funzione restituisce un valore (cioè termina), viene rimossa dallo stack.
Però questo stack ha una dimensione limitata.
L'errore più comune è una funzione ricorsiva che non termina mai.
Ogni chiamata viene messa sullo stack, ma prima che restituisca, un'altra chiamata viene messa sullo stack.
function kaboom() {
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
La traccia dello stack di questo errore mostra sempre la stessa riga, il che ha senso, perché la funzione chiama se stessa.
Anche se nella maggior parte dei casi non ha una vera utilità pratica, puoi scoprire quanto può diventare alto quello stack.
let calls = 0;
function kaboom() {
calls +=1 ;
kaboom()
}
kaboom()
// => RangeError: Maximum call stack size exceeded
console.log(calls)
// => a number, generally higher than 10.000
Ci sono solo due soluzioni valide a un errore di stack causato da una funzione ricorsiva sincrona:
- assicurarti che le funzioni restituiscano un valore prima di raggiungere il limite dello stack, di solito aggiungendo o correggendo un caso base.
- riscrivere la funzione ricorsiva come un ciclo imperativo, che eseguirà il corpo del ciclo senza dover entrare in una funzione, e quindi senza aumentare lo stack.
Esercizio di apprendimento
