Guida C interattiva: Ricorsione

Q: Cos'è la ricorsione in C?

Una funzione che chiama se stessa per risolvere una versione più piccola dello stesso problema. Ogni funzione ricorsiva ha bisogno di due cose: un caso base che restituisce un valore senza richiamarsi e un caso ricorsivo che si avvicina in modo misurabile al caso base. Senza caso base le chiamate non si fermano mai e il programma va in crash con uno stack overflow.

Q: Come si scrive una funzione fattoriale in C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Il caso base gestisce 0 e 1, e ogni chiamata ricorsiva riduce n di uno finché non lo raggiunge. Tieni presente che un int va in overflow a 13!: usa unsigned long long per valori più grandi.

Q: Perché il Fibonacci ricorsivo è così lento in C?

Perché fib(n) chiama fib(n-1) e fib(n-2), che ricalcolano gli stessi sottoproblemi di continuo: il numero di chiamate cresce in modo esponenziale, quindi fib(50) richiederebbe anni. Riscriverlo come un ciclo che tiene gli ultimi due valori lo rende lineare e istantaneo.

Q: Cosa causa uno stack overflow nella ricorsione in C?

Ogni chiamata occupa un frame di memoria sullo stack per i suoi parametri e le sue variabili locali, e lo stack è di pochi megabyte. Un caso base mancante o irraggiungibile significa ricorsione infinita e un crash immediato; anche una ricorsione corretta che scende di centinaia di migliaia di livelli può esaurire lo stack.

Una funzione che chiama se stessa

Niente impedisce a una funzione C di chiamare se stessa. Il suo nome è visibile all'interno del corpo, quindi questo è lecito:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* chiama se stessa, ma non si ferma mai! */
}

Ed è anche sbagliato. Stampa all'infinito, anche numeri negativi, finché il programma non va in crash. Gli manca un caso base: una condizione in cui la funzione restituisce il controllo senza chiamare se stessa.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* caso base: fermati */
        printf("Decollo!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* caso ricorsivo: un problema piu piccolo */
}

int main(void) {
    countdown(5);
    return 0;
}

Ogni funzione ricorsiva ha esattamente queste due parti:

Un caso base: l'input più piccolo, a cui si risponde direttamente, senza ulteriori chiamate.
Un caso ricorsivo: risolve il problema tramite una versione strettamente più piccola di se stesso.

"Strettamente più piccola" è la parte che si sbaglia. countdown(n - 1) si avvicina a 0 a ogni chiamata. countdown(n) non lo farebbe, e nemmeno countdown(n / 2) se n potesse restare 1 per sempre. Ogni percorso deve ridurre il problema, altrimenti il caso base non viene mai raggiunto.

Fattoriale

Il primo esempio classico. n! è n × (n-1) × ... × 1, e 0! è definito come 1. Quella definizione è già ricorsiva: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* caso base: 0! e 1! valgono entrambi 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* caso ricorsivo */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Segui factorial(4) per vedere come si costruisce la risposta. Le chiamate scendono e le moltiplicazioni avvengono durante la risalita:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (caso base)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Non si moltiplica nulla finché il caso base non restituisce il valore. Ogni chiamata in sospeso resta in attesa tenendo il proprio n, ed è questo il punto da interiorizzare: quelle chiamate in attesa occupano memoria.

Nota il tipo di ritorno. int va in overflow intorno a 13!, producendo in silenzio un numero sbagliato: il C non controlla. unsigned long long ti porta fino a 20! e non oltre, perché 21! supera i 64 bit. Qui il limite non è la ricorsione, è il tipo.

Il caso base usa n <= 1 invece di n == 1 di proposito: factorial(0) deve valere 1, e <= lo gestisce. Con n == 1, chiamare factorial(0) scenderebbe a -1, -2 e non terminerebbe mai: un buon esempio di come un caso base "ovviamente corretto" possa dimenticare un input.

Fibonacci, e perché la versione ingenua è una trappola

Fibonacci è l'altro classico: ogni numero è la somma dei due precedenti, partendo da 0 e 1. La definizione ricorsiva si scrive da sola.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld chiamate)\n", n, result, calls);
    }
    return 0;
}

Guarda il numero di chiamate. fib(10) richiede 177 chiamate; fib(35) quasi 30 milioni. Ogni passo di 5 moltiplica il lavoro per circa undici.

Il motivo si vede nell'albero delle chiamate. fib(5) chiama fib(4) e fib(3); fib(4) chiama di nuovo fib(3); e ognuna di queste ricalcola fib(2) da zero. Nulla viene ricordato, quindi gli stessi sottoproblemi vengono risolti più e più volte e il numero di chiamate cresce all'incirca come 1,6ⁿ. fib(50) in questo modo girerebbe per giorni; fib(100) durerebbe più dell'universo.

La versione con il ciclo tiene gli ultimi due valori ed è lineare:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) risponde all'istante. La lezione non è "la ricorsione è lenta": è che la ricorsione con sottoproblemi sovrapposti è lenta, a meno che tu non ricordi le risposte. Salva i risultati in un array mentre li calcoli (memoizzazione) e anche la versione ricorsiva diventa lineare.

Il call stack e lo stack overflow

Ogni chiamata di funzione ha bisogno di un posto dove tenere i parametri, le variabili locali e l'indirizzo a cui tornare. Quello spazio è uno stack frame, che viene aggiunto quando la chiamata inizia e rimosso quando restituisce. La ricorsione impila i frame uno sopra l'altro: factorial(1000) ha mille frame attivi contemporaneamente, ognuno con il proprio n.

Lo stack non è grande. Un valore predefinito tipico è 1-8 MB, quindi qualche decina di migliaia di frame è il limite realistico, e molto meno se ogni frame contiene un grosso array locale. Superalo e il programma muore:

Segmentation fault (core dumped)

Quello è uno stack overflow, e ci si arriva in due modi:

Ricorsione infinita: un caso base mancante o irraggiungibile. È un bug, e il crash è immediato:

int bad(int n) {
    return bad(n - 1);      /* nessun caso base: crash in una frazione di secondo */
}

Corretta ma troppo profonda: una chiamata ricorsiva per ogni elemento di una lista da un milione di voci. La logica è giusta, ma l'approccio non entra nello stack. Riscrivila come un ciclo, oppure ristrutturala in modo che la profondità sia logaritmica (ricorrere sulle metà, come fanno la ricerca binaria e il merge sort, dà una profondità di circa 20 per un milione di elementi).

Alcuni compilatori riescono a trasformare la ricorsione in coda, in cui la chiamata ricorsiva è l'ultimissima cosa che la funzione fa, senza lavoro in sospeso dopo, in un ciclo che riusa un solo frame. countdown qui sopra è ricorsiva in coda; factorial no, perché la moltiplicazione deve ancora avvenire dopo che la chiamata restituisce. Ma il C non impone questa ottimizzazione, quindi può avvenire o meno a seconda del compilatore e delle opzioni. Non scrivere mai codice C che funziona solo perché l'ottimizzatore ha eliminato una chiamata in coda.

Dove la ricorsione vince davvero

Ogni funzione ricorsiva si può riscrivere come ciclo, e per un semplice conteggio il ciclo è chiaramente migliore. La ricorsione si guadagna il posto quando sono i dati stessi a essere ricorsivi, cioè quando una struttura contiene copie più piccole di se stessa.

La ricerca binaria è un esempio pulito: cerca in una metà, poi nella metà di quella.

#include <stdio.h>

/* restituisce l'indice di target, oppure -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* caso base: non resta nulla */
    }
    int mid = low + (high - low) / 2;       /* evita l'overflow con indici grandi */

    if (a[mid] == target) {
        return mid;                         /* caso base: trovato */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> indice %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Qui ci sono due casi base, ed è normale: uno per il successo e uno per l'esaurimento. La profondità è circa log₂(n), quindi anche un miliardo di elementi richiede solo trenta frame.

Altri casi in cui la ricorsione è la scelta naturale: attraversare un albero o una lista concatenata, percorrere le directory, analizzare espressioni annidate e gli ordinamenti divide et impera come quicksort e merge sort. In tutti questi il codice ricorsivo è più corto e più chiaro del ciclo con uno stack esplicito che lo sostituirebbe.

Ricorsione o ciclo?

Usa un ciclo quando          il problema e lineare: contare, sommare, scorrere
Usa la ricorsione quando     i dati sono annidati: alberi, strutture annidate, divide et impera
Riscrivi la ricorsione       se la profondita puo crescere senza limite con la dimensione dell'input
Non usare mai la ricorsione  quando i sottoproblemi si sovrappongono, a meno di memoizzare

Due note pratiche. Le chiamate ricorsive costano un po' più di un'iterazione di ciclo, perché ogni volta c'è un frame da aggiungere e rimuovere, quindi per cicli semplici e molto usati la versione iterativa vince in velocità oltre che in memoria. E il debug è diverso: uno stack trace di una ricorsione profonda è fatto di centinaia di frame tutti uguali, quindi stampa il parametro in ingresso (come fa il contatore calls qui sopra) quando qualcosa non termina.

Scrivere una funzione ricorsiva: una checklist

Trova prima il caso base. Qual è l'input più piccolo e qual è la sua risposta? Se non sai dirlo, la funzione non si può scrivere.
Dai per scontato che la chiamata ricorsiva funzioni. Non seguirla a mente: fidati che factorial(n - 1) restituisca (n-1)! e scrivi l'unico passo che lo trasforma nella risposta.
Controlla che ogni percorso riduca il problema. Ogni chiamata ricorsiva deve avvicinarsi al caso base per ogni input possibile, compresi 0 e i negativi.
Controlla la profondità. Più o meno quanti frame raggiungerà con dati reali? Migliaia vanno bene; milioni no.
Controlla le sovrapposizioni. Se lo stesso sottoproblema viene calcolato due volte, ti serve la memoizzazione o un ciclo.

Domande frequenti

Cos'è la ricorsione in C?

Una funzione che chiama se stessa per risolvere una versione più piccola dello stesso problema. Ogni funzione ricorsiva ha bisogno di due cose: un caso base che restituisce un valore senza richiamarsi e un caso ricorsivo che si avvicina in modo misurabile al caso base. Senza caso base le chiamate non si fermano mai e il programma va in crash con uno stack overflow.

Come si scrive una funzione fattoriale in C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Il caso base gestisce 0 e 1, e ogni chiamata ricorsiva riduce n di uno finché non lo raggiunge. Tieni presente che un int va in overflow a 13!: usa unsigned long long per valori più grandi.

Perché il Fibonacci ricorsivo è così lento in C?

Perché fib(n) chiama fib(n-1) e fib(n-2), che ricalcolano gli stessi sottoproblemi di continuo: il numero di chiamate cresce in modo esponenziale, quindi fib(50) richiederebbe anni. Riscriverlo come un ciclo che tiene gli ultimi due valori lo rende lineare e istantaneo.

Cosa causa uno stack overflow nella ricorsione in C?

Ogni chiamata occupa un frame di memoria sullo stack per i suoi parametri e le sue variabili locali, e lo stack è di pochi megabyte. Un caso base mancante o irraggiungibile significa ricorsione infinita e un crash immediato; anche una ricorsione corretta che scende di centinaia di migliaia di livelli può esaurire lo stack.

Concetti correlati