Ricorsione

Definizioni ricorsive

Il fattoriale

Il fattoriale di un naturale $n$ è il prodotto dei naturali da 1 a $n$: $n! = 1 \cdot 2 \cdots n$, con la convenzione $0! = 1$. I puntini di sospensione di quella formula nascondono un ciclo, e la lezione Cicli ha insegnato a scriverlo. Ora, la stessa definizione ammette un’altra forma, che non menziona alcun ciclo: il fattoriale di $n$ è $n$ volte il fattoriale di $n - 1$, e quello di 0 è 1.

Questa è una definizione ricorsiva: definisce il fattoriale di $n$ per mezzo del fattoriale di un numero minore. Non è circolare, perché ogni applicazione della seconda regola scende di un gradino e la scala termina nella prima: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. Le due regole hanno un nome. La prima è il caso base, che dà il risultato senza riferirsi ad altro; la seconda è il caso ricorsivo, che riduce il problema a un’istanza più piccola dello stesso problema.

C++ permette a una funzione di chiamare sé stessa, e con ciò la definizione si traduce quasi parola per parola.

#include <print>​// Fattoriale di n.// Precondizione: 0 <= n <= 12 (il limite si giustifica più avanti).// Postcondizione: restituisce n! = 1 · 2 · ... · n, con 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // caso base    }    return n * factorial(n - 1);    // caso ricorsivo}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

Il contratto non è decorativo: con $n = -1$ il caso ricorsivo chiamerebbe con $-2$, poi con $-3$, e non raggiungerebbe mai lo 0; e $13!$ non sta in un int. Molti testi introduttivi scrivono questo fattoriale con il caso base if (n == 0 || n == 1), ridondante ma innocuo, e senza dire nulla dei negativi né della grandezza del risultato: il loro codice non termina con $n < 0$ e dà un risultato privo di senso a partire da $13!$. Entrambi i difetti saranno esaminati nella loro sezione.

Caso base e caso ricorsivo

Ogni funzione ricorsiva ha uno o più casi base, che si risolvono direttamente, e uno o più casi ricorsivi, che chiamano la stessa funzione con un argomento minore in un senso preciso e combinano ciò che essa restituisce.

La potenza $x^n$, con $n$ naturale, si definisce con $x^0 = 1$ e $x^n = x \cdot x^{n - 1}$: la dimensione è l’esponente. La somma delle cifre di un naturale $n$ (quella di 2026 è $2 + 0 + 2 + 6 = 10$) si definisce così: se $n < 10$, la somma è $n$, perché ha una sola cifra; altrimenti, è la somma delle cifre di $\lfloor n / 10 \rfloor$, che è $n$ senza la sua ultima cifra, più quest’ultima cifra, $n \bmod 10$. Qui la dimensione è il numero di cifre.

#include <print>​// x elevato alla n.// Precondizione: n >= 0.// Postcondizione: restituisce x^n, con x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Somma delle cifre decimali di n.// Precondizione: n >= 0.// Postcondizione: restituisce la somma delle cifre di n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("somma delle cifre di 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375somma delle cifre di 2026: 10

Scrivere una funzione ricorsiva consiste, dunque, nel rispondere a due domande: quali casi si risolvono senza aiuto, e come si ottiene la soluzione di un caso a partire da quella di uno minore. Se entrambe le risposte sono corrette, lo è anche la funzione, e la sezione seguente lo dimostra.