Che Cos'è la Ricorsione? Funzioni Ricorsive in JavaScript Spiegate con Esempi di Codice

Articolo originale: What is Recursion? A Recursive Function Explained with JavaScript Code Examples

La ricorsione è una tecnica usata per risolvere problemi computazionali attraverso una funzione che invoca sé stessa fino a quando il programma ottiene il risultato desiderato.

Questo tutorial ti consentirà di imparare cos'è ricorsione e quali sono le differenze rispetto ai più comuni loop.

Che cos'è la ricorsione?

Prendiamo come esempio una funzione che mostra nella console i numeri da 1 a 5. Ecco come possiamo scriverla usando la ricorsione:

function log(num){
    if(num > 5){
        return;
    }
    console.log(num);
    log(num + 1);
}

log(1);

Quando questo codice è eseguito, la funzione log continua a invocare sé stessa fino a quando il valore della variabile num è minore di 5.

Una funzione ricorsiva deve avere almeno una condizione che porti la funzione a smettere di invocarsi. Se la funzione continua a invocarsi, a un certo punto JavaScript darà errore.

La condizione che consente alla funzione ricorsiva di smettere di invocare sé stessa si chiama caso base. Nella funzione log sopra, il caso base e quando num è maggiore di 5.

Perché non usare un ciclo?

Qualsiasi problema che possiamo risolvere con una funzione ricorsiva può sempre essere risolto con una soluzione iterativa. L'esempio precedente può essere sostituito con questo codice:

for(let i = 1; i <= 5; i++){
    console.log(i);
}

I linguaggi di programmazione moderni come JavaScript possiedono istruzioni come for e while che forniscono alternative alle funzioni ricorsive. Tuttavia, esistono linguaggi come Clojure che non includono dichiarazioni di cicli, quindi in questi casi abbiamo bisogno di usare la ricorsione per ripetere parti del codice.

Inoltre, per usare un ciclo for è necessario sapere quante volte il codice dovrà essere ripetuto. Le funzioni ricorsive e il ciclo while invece possono essere usate per eseguire una parte di codice senza sapere quante volte sarà necessario ripeterlo. L'unica cosa che basta sapere è la condizione che fermerà l'esecuzione del codice.

Per esempio, immagina di dover risolvere questo problema:

• Scegli un numero a caso tra 1 e 10 fino a quando ottieni 5.
• Registra quante volte il codice è stato eseguito prima di ottenere 5.

Ecco la soluzione usando una funzione ricorsiva:

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        console.log(`Il risultato casuale: ${result}`);
        console.log(`Numero di esecuzioni del codice: ${count}`);
        return;
    }
    result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
    count++;
    randomUntilFive(result, count);
}

randomUntilFive();

Non è possible sostituire il codice qui sopra con un ciclo for, ma è possibile farlo con un ciclo while:

let result = 0;
let count = 0;

while (result !== 5) {
  result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
  count++;
}

console.log(`Il risultato casuale: ${result}`);
console.log(`Numero di esecuzioni del codice: ${count}`);

Ad esclusione dei colloqui di lavoro in cui ti può essere chiesto di risolvere un problema usando la ricorsione, puoi sempre trovare una soluzione alternativa che usa i cicli for o while.

Come leggere una funzione ricorsiva

Una funzione ricorsiva non è facile o intuitiva da capire a prima vista. I seguenti punti ti aiuteranno a leggere e capire una funzione ricorsiva velocemente.

1. Prima di tutto, identifica sempre qual è il caso base;
2. Passa argomenti nella funzione che raggiungono immediatamente il caso base;
3. Includi argomenti che consentiranno almeno una iterazione della funzione ricorsiva.

Proviamo a seguire questi passaggi usando l'esempio precedente di randomUntilFive(). Puoi identificare il caso base per questa funzione all'interno dell'istruzione if:

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        // il caso base è attivato
    }
    // la funzione è invocata ricorsivamente
}

randomUntilFive();

Questo significa che puoi raggiungere il caso base passando il numero 5 nel parametro result come segue:

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        console.log(`Il risultato casuale: ${result}`);
        console.log(`Numero di esecuzioni del codice: ${count}`);
        return;
    }
}

randomUntilFive(5);

Il parametro count non dovrebbe essere zero. Tuttavia, se passiamo il numero 5 come argomento della funzione sopra allora soddisfiamo il requisito del punto 2.

Infine, dobbiamo trovare un argomento che ci consenta di eseguire la funzione ricorsiva una volta. Nel caso qui sopra, possiamo passare qualsiasi numero tranne 5, oppure possiamo anche non passare alcun argomento:

function randomUntilFive(result = 0, count = 0){
    if(result === 5){
        console.log(`Il risultato casuale: ${result}`);
        console.log(`Numero di esecuzioni del codice: ${count}`);
        return;
    }
    result = Math.floor(Math.random() * (10 - 1 + 1) + 1);
    count++;
    randomUntilFive(result, count);
}

randomUntilFive(4); 
// qualsiasi numero diverso da 5
// eseguirà la ricorsione

Ecco fatto. Ora abbiamo capito che la funzione randomUntilFive() invocherà sé stessa ricorsivamente fino a quando il valore di result non sarà 5.

Come scrivere una funzione ricorsiva

Scrivere una funzione ricorsiva non è molto diverso da leggerne una.

1. Crea una funzione regolare con un caso base che può essere raggiunto con i suoi parametri;
2. Passa argomenti nella funzione che attivano immediatamente il caso base;
3. Passa argomenti che attivano la ricorsione una volta sola.

Prendiamo l'esempio di una funzione per il calcolo di fattoriali. Ecco il fattoriale di cinque:

5*4*3*2*1 = 120

Il caso base di questa funzione è uno, quindi creiamo una funzione factorial che restituisce uno:

function factorial(num){
    if(num === 1){
        return num;
    }
    
}

console.log(factorial(1));

Ora, andiamo al passo 3. Abbiamo bisogno di raggiungere la chiamata ricorsiva nella funzione e invocarla almeno una volta. Visto che il calcolo fattoriale diminuisce il numero di uno ad ogni moltiplicazione, possiamo simulare questo caso passando l'argomento num-1 nella chiamata ricorsiva:

function factorial(num){
    if(num === 1){
        return num;
    }
    return num * factorial(num-1) 
}

console.log(factorial(2));

Abbiamo finito. Puoi testare la funzione passando 5 come argomento:

console.log(factorial(5));

Conclusione

Abbiamo imparato che cos'è una funzione ricorsiva e quali sono le differenze tra questo tipo di funzione e le comuni istruzioni di ciclo for e while. Una funzione ricorsiva deve sempre avere almeno un caso base affinché eviti di invocare sé stessa all'infinito. In caso contrario, la funzione darà un errore.

Quando leggiamo una funzione ricorsiva, dobbiamo simulare una situazione dove il caso base è eseguito immediatamente senza eseguire la chiamata ricorsiva.

Quando abbiamo trovato il caso base, facciamo un passo indietro e proviamo a eseguire la chiamata ricorsiva almeno una volta. In questo modo, la tua mente percorrerà il codice ricorsivo e capirà intuitivamente come funziona.

Lo stesso vale per quando dobbiamo scrivere una funzione ricorsiva. È bene pensare sempre al caso base all'inizio, e poi includere un argomento nella funzione che faccia eseguire la chiamata ricorsiva almeno una volta. Dopo aver fatto questo, tutto il resto sarà facile.

Grazie per aver letto questo tutorial

Se questo articolo ti è piaciuto e vuoi migliorare le tue abilità in JavaScript, ti consiglio di leggere il mio nuovo libro Beginning Modern JavaScript qui.

Questo libro è pensato per essere facile da capire e accessibile per chiunque voglia imparare JavaScript. Le sue semplici guide passo-passo ti aiuteranno a capire come usare JavaScript per creare un'applicazione dinamica.

Ti prometto che capirai davvero cosa stai facendo con JavaScript.

Alla prossima!