Introduzione alla ricorsione

La ricorsione è una tecnica di programmazione in cui una funzione chiama sé stessa per risolvere un problema. Invece di usare cicli, le funzioni ricorsive scompongono i problemi complessi in sottoproblemi più piccoli e simili, finché non raggiungono un caso semplice che può essere risolto direttamente.

Ogni funzione ricorsiva deve avere due componenti essenziali. Il caso base è una condizione che interrompe la ricorsione: senza di essa, la funzione chiamerebbe se stessa all'infinito. Il passo ricorsivo è il punto in cui la funzione chiama se stessa con parametri modificati, avvicinandosi al caso base a ogni chiamata.

Ecco un semplice esempio di conto alla rovescia che mostra la ricorsione:

void countdown(int n) {
    if (n <= 0) {           // Caso base: fermati quando n raggiunge 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Passo ricorsivo: chiama con n-1
}

Quando chiami countdown(3), stampa 3, poi chiama countdown(2), che stampa 2, poi chiama countdown(1) e così via fino a raggiungere il caso base. Ogni chiamata di funzione attende che quella successiva venga completata prima di terminare, creando una catena di chiamate che alla fine si risolve tornando al chiamante originale.