Ricorsione: fattoriale, Fibonacci e MCD di Euclide

Inizio ottobre 2026: nelle terze di informatica degli istituti tecnici (e nelle terze del liceo scientifico scienze applicate) dopo cicli, array e funzioni arriva la ricorsione: una funzione che richiama sé stessa. Di solito si fa fra ottobre e novembre e la verifica pratica in laboratorio cade fra cinque e nove settimane da ora. Il tema spaventa perché le righe sono poche e sembrano magia. Non lo è: basta una regola e un metodo per tracciare a mano.

Che cos’è la ricorsione

Una funzione è ricorsiva se, per risolvere un problema di taglia $n$, risolve lo stesso problema su una taglia più piccola e poi combina il risultato. Ogni funzione ricorsiva ha due parti obbligatorie.

• Caso base: la situazione così piccola che la risposta è già nota, senza altre chiamate (per il fattoriale: $0!=1$).
• Passo ricorsivo: riduce il problema e richiama la funzione su un valore più vicino al caso base (per il fattoriale: $n!=n\cdot (n-1)!$).

Se manca uno dei due, il programma non funziona. Prima di scrivere codice, scrivi queste due righe in italiano.

La pila delle chiamate

Quando una funzione ne chiama un’altra, la prima resta in attesa: il computer la mette in una pila (stack) e ci torna quando la seconda ha finito. Con la ricorsione la pila cresce a ogni chiamata e si svuota quando si arriva al caso base e i valori tornano indietro. Tracciare a mano questa pila è l’abilità che ti verifica ogni prova.

Traccia di fattoriale(4)

int fattoriale(int n) {
    if (n == 0) return 1;              // caso base
    return n * fattoriale(n - 1);      // passo ricorsivo
}

Risultato: $4!=24$. Nota che i prodotti vengono calcolati al ritorno, dal basso verso l’alto: finché non si arriva a fattoriale(0) nessuna moltiplicazione è stata fatta.

La stessa funzione in Python:

def fattoriale(n):
    if n == 0:
        return 1
    return n * fattoriale(n - 1)

print(fattoriale(4))   # 24

Fibonacci: perché la versione ingenua è lenta

La successione: $F_0=0$, $F_1=1$, e ogni termine è la somma dei due precedenti. Qui i casi base sono due.

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n - 1) + fib(n - 2)

print(fib(5))   # 5

Il passo ricorsivo chiama sé stessa due volte: ogni chiamata ne genera altre due, e molte sono ripetute. Contiamole per fib(5). Se $C(n)$ è il numero di chiamate totali di fib(n), vale $C(0)=C(1)=1$ e $C(n)=1+C(n-1)+C(n-2)$:

Quindi fib(5) fa 15 chiamate per restituire 5. Dentro, fib(3) viene calcolata due volte, fib(2) tre volte. Con $n=40$ le chiamate sono centinaia di milioni: ecco perché il programma «si pianta». Il costo cresce in modo esponenziale (se hai già visto la notazione O-grande, è la differenza fra $O(n)$ e un costo esponenziale). La versione iterativa, che tiene solo gli ultimi due valori, fa $n$ passi:

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_iter(5))   # 5

In C++ puoi verificare il conteggio con un contatore globale:

#include <iostream>
using namespace std;

int chiamate = 0;

int fib(int n) {
    chiamate++;
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    cout << fib(5) << endl;        // 5
    cout << chiamate << endl;      // 15
    return 0;
}

MCD di Euclide

L’algoritmo di Euclide si basa su una proprietà: $\text{mcd}(a,b)=\text{mcd}(b,a\mathrm{mod}b)$, e $\text{mcd}(a,0)=a$. Il caso base è $b=0$, il passo ricorsivo sostituisce la coppia con una coppia dove il secondo numero è più piccolo: si avvicina sempre a 0.

int mcd(int a, int b) {
    if (b == 0) return a;
    return mcd(b, a % b);
}

Rifacciamo mcd(48, 18) passo per passo.

Il risultato risale invariato: $\text{mcd}(48,18)=6$. In questo caso la ricorsione è «di coda»: non resta nulla da fare al ritorno, e la versione con un ciclo while è equivalente.

Ricorsione o iterazione?

Ogni funzione ricorsiva si può scrivere con un ciclo, e viceversa. La ricorsione è più naturale quando il problema ha una struttura che si ripete su sé stessa (alberi, divisioni a metà, fattoriale, Euclide); l’iterazione è più economica in memoria, perché non riempie la pila. Regola pratica per la verifica: se il testo dice «ricorsiva», scrivi ricorsiva; se non lo dice e hai dubbi, un ciclo è quasi sempre più sicuro. Ma devi saper fare tutte e due.

Gli errori che costano punti

1. Caso base mancante. La funzione si richiama all’infinito, la pila si riempie e il programma si ferma con un errore di stack overflow (in Python, RecursionError: il limite predefinito è circa mille chiamate).

2. Caso base sbagliato. Questo è il più insidioso. Se scrivi if (n == 1) return 1; e chiami fattoriale(0), la sequenza è 0, -1, -2, … e n == 1 non scatta mai.

3. Non avvicinarsi al caso base. Se nel passo ricorsivo scrivi fattoriale(n) invece di fattoriale(n - 1), la chiamata è identica a sé stessa. Oppure sbagli segno e vai nella direzione opposta.

4. Dimenticare il return davanti alla chiamata. fattoriale(n - 1) da sola calcola e butta via il valore.

5. Overflow dei numeri. Con int a 32 bit, $12!=479001600$ ci sta, $13!=6227020800$ no: il risultato è sbagliato senza errori. Non è un errore di ricorsione, ma salta fuori quando provi valori grandi.

Tre esercizi svolti

Esercizio 1: potenza ricorsiva

Scrivi potenza(b, e) che calcola $b^e$ per $e\ge 0$ senza usare pow.

Ragionamento: $b^0=1$ (caso base), $b^e=b\cdot b^{e-1}$ (passo ricorsivo; $e$ diminuisce di 1 e arriva a 0).

def potenza(b, e):
    if e == 0:
        return 1
    return b * potenza(b, e - 1)

print(potenza(2, 5))   # 32

Traccia di potenza(2, 5): scende fino a potenza(2, 0) = 1, poi risale: $2\cdot 1=2$, $2\cdot 2=4$, $2\cdot 4=8$, $2\cdot 8=16$, $2\cdot 16=32$. Cinque moltiplicazioni, risultato 32.

Esercizio 2: somma delle cifre

Scrivi una funzione che, dato un intero positivo, restituisce la somma delle sue cifre.

Idea: l’ultima cifra è n % 10, il resto del numero è n / 10 (divisione intera). Caso base: se n < 10 la somma è n stesso.

#include <iostream>
using namespace std;

int sommaCifre(int n) {
    if (n < 10) return n;
    return n % 10 + sommaCifre(n / 10);
}

int main() {
    cout << sommaCifre(472) << endl;   // 13
    return 0;
}

Traccia: sommaCifre(472) = $2+$ sommaCifre(47); sommaCifre(47) = $7+$ sommaCifre(4); sommaCifre(4) = 4 (caso base). Risalendo: $7+4=11$, poi $2+11=13$. Output: 13.

Esercizio 3: trova l’errore

Questo codice dovrebbe calcolare il fattoriale:

int fattoriale(int n) {
    if (n == 1) return 1;
    return n * fattoriale(n - 1);
}

Che cosa succede con fattoriale(3)? E con fattoriale(0)?

• fattoriale(3): 3 → 2 → 1, e n == 1 ferma la discesa. Risale: $2\cdot 1=2$, $3\cdot 2=6$. Funziona.
• fattoriale(0): la sequenza è 0, -1, -2, -3, … senza mai toccare 1. Non c’è un punto d’arresto, e dopo qualche migliaio di chiamate il programma termina per stack overflow.

Correzione: caso base if (n <= 1) return 1;, che copre sia 0 sia 1 (e, per sicurezza, i negativi, anche se in teoria il fattoriale non è definito per loro).

Allenarsi: che cosa c’è sul sito

Di informatica non esiste ancora una simulazione dedicata, e non ti prometto che arrivi. Sul sito trovi la pagina simulazioni con quello che c’è oggi, ma per la ricorsione l’allenamento utile è un altro: prendi i tre esercizi qui sopra, riscrivili senza guardare, poi traccia a mano la pila con carta e penna. Se il computer ti dà ragione, hai capito.

Dove si collega

La ricorsione usa tutto quello che hai appena studiato. Se i cicli e gli array ti sembrano ancora scivolosi, parti da cicli annidati e array in terza. La traccia della pila ha senso solo se hai chiaro come una funzione riceve i parametri: lo trovi in funzioni, valore e riferimento. E se vuoi capire perché la fib ingenua è lenta in termini formali, c’è complessità e O-grande, scritto per l’università ma con le stesse idee. La pagina generale è informatica.

Come lavoriamo nelle lezioni

Con la ricorsione faccio sempre la stessa cosa: prima scrivi caso base e passo in italiano, poi il codice, poi la traccia a mano della pila su un valore piccolo, e solo dopo premi «esegui». Se il programma dà un risultato che non ti aspettavi, torni alla traccia e cerchi il passo in cui la tua previsione e il programma divergono. Non è veloce all’inizio, ma è l’unico modo per smettere di scrivere ricorsioni «a tentativi». Il codice che scriviamo è il tuo, sul tuo editor, con gli esercizi del tuo libro.

Se vuoi capire da dove ripartire senza impegno, la diagnosi gratuita è il modo più semplice. Per le modalità c’è la pagina pricing.