Basi della ricorsione

La ricorsione è una tecnica in cui una funzione richiama sé stessa per risolvere un problema. È come risolvere un problema grande suddividendolo in problemi più piccoli e simili.

Esaminiamo una semplice funzione ricorsiva che calcola il fattoriale:

int factorial(int n) {
    // Caso base: il fattoriale di 0 o 1 è 1
    if (n <= 1) {
        return 1;
    }
    
    // Caso ricorsivo: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Ogni funzione ricorsiva ha bisogno di:

1. Un caso base per interrompere la ricorsione
2. Un caso ricorsivo che si avvicina al caso base

Ad esempio, calcolare factorial(3):

• factorial(3) chiama factorial(2)
• factorial(2) chiama factorial(1)
• factorial(1) restituisce 1 (caso base)

• factorial(2) restituisce 2 * 1 = 2
• factorial(3) restituisce 3 * 2 = 6