Funzioni Ricorsive in Linguaggio C

La Ricorsione è un concetto fondamentale in informatica e in programmazione. Una funzione ricorsiva è una funzione che chiama se stessa.

Il linguaggio C permette di implementare funzioni ricorsive in modo semplice e diretto. In questa lezione vedremo come fare e quali sono le implicazioni della ricorsione in C.

La Ricorsione

Abbiamo visto che in linguaggio C una funzione può chiamare un'altra funzione che, a sua volta, ne può chiamare un'altra e così via. Questo meccanismo è alla base della modularità del codice e ci permette di scomporre problemi più complessi in problemi più semplici.

Esiste, però, anche la possibilità che una funzione possa chiamare se stessa. Questo meccanismo è chiamato ricorsione e permette di risolvere problemi complessi in modo elegante e conciso.

Una funzione ricorsiva, infatti, è una funzione definita in termini di se stessa.

Molti linguaggi di programmazione si basano completamente sulla ricorsione per la risoluzione di problemi. Altri linguaggi, invece, la vietano non permettendo la chiamata ricorsiva di funzioni.

In questo senso, il linguaggio C è un linguaggio di programmazione che permette la ricorsione, ma non la incoraggia. Questo perché la ricorsione può portare a problemi di prestazioni e di memoria, se non utilizzata correttamente.

L'esempio classico per introdurre il concetto è quello della funzione fattoriale.

La funzione fattoriale è definita matematicamente come:

n! = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1

Ma può essere riscritta in forma ricorsiva, ossia in termini di se stessa:

n! = \left\{ \begin{array}{ll} 1 &amp; \text{se } n \leq 1 \\ n \cdot (n-1)! &amp; \text{altrimenti} \end{array} \right.

In questo caso, la funzione fattoriale è definita in termini di se stessa: il fattoriale di $n$ è uguale a $n$ moltiplicato per il fattoriale di $n-1$ .

Una qualunque funzione ricorsiva può anche essere scritta in forma iterativa, ossia senza utilizzare la ricorsione e viceversa. Lo stesso vale per qualunque algoritmo ricorsivo, che può essere riscritto in forma iterativa e viceversa.

Da questo punto di vista, la funzione fattoriale rappresenta proprio un esempio classico di questa dualità.

Proviamo, quindi, ad implementare una prima versione della funzione fattoriale in forma iterativa, ossia usando un ciclo for:

int fattoriale_iterativo(int n) {
    int fattoriale = 1;
    for (int i = 1; i <= n; i++) {
        fattoriale *= i;
    }
    return fattoriale;
}

In questo caso, la funzione fattoriale_iterativo calcola il fattoriale di un numero intero n in modo iterativo, moltiplicando tutti i numeri da 1 a n. Abbiamo usato, cioè, la prima definizione matematica del fattoriale vista sopra.

Proviamo ora ad implementare la funzione fattoriale in forma ricorsiva:

int fattoriale_ricorsivo(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * fattoriale_ricorsivo(n - 1);
    }
}

La prima osservazione è che la funzione nel proprio corpo richiama ad un certo punto se stessa. Non è necessaria alcuna sintassi particolare. Questa è una delle caratteristiche della ricorsione in C: non è necessario alcun costrutto particolare per chiamare una funzione ricorsiva. In altri linguaggi invece, bisogna esplicitamente dichiarare una funzione come ricorsiva, come ad esempio in FORTRAN.

Definizione

Funzione Ricorsiva in Linguaggio C

Una funzione ricorsiva è una funzione che invoca direttamente se stessa nel proprio corpo.

tipo_ritorno funzione(parametri) {
    /* ... */
    funzione(parametri);
    /* ... */
}

Adesso, proviamo ad analizzare cosa accade se invochiamo la versione ricorsiva in questo modo:

int main() {
    int n = 3;
    printf("Il fattoriale di %d è %d\n", n, fattoriale_ricorsivo(n));
    return 0;
}

In questo esempio, stiamo invocando la funzione con un parametro 3:

**Figura 1:** Invocazione della funzione fattoriale con Argomento pari a 3

All'interno della funzione, l'istruzione if selezionerà il ramo else in quanto n è maggiore di 1. Per cui, la funzione invocherà di nuovo se stessa ma stavolta con parametro 2. La catena di chiamata diventerà:

**Figura 2:** Catena delle chiamate dopo la prima chiamata ricorsiva

Allo stesso modo, la funzione fattoriale_ricorsivo(2) chiamerà a sua volta fattoriale_ricorsivo(1):

**Figura 3:** Catena delle chiamate dopo la seconda chiamata ricorsiva

Quando viene invocata con il parametro 1, la funzione entrerà nel ramo if e restituirà 1. Questo ramo prende il nome speciale di caso base ed è quella condizione che interrompe la ricorsione:

**Figura 4:** Raggiungimento del caso base

Da notare che le chiamate alla funzione ricorsiva in un primo momento si impilano una sopra l'altra, fino a raggiungere il caso base. Questa prima fase prende il nome di Pile Up.

Raggiunto il caso base, le chiamate vengono risolte una alla volta, partendo dall'ultima chiamata effettuata.

Per cui, il risultato della chiamata fattoriale_ricorsivo(1), ossia 1, viene sostituito nella chiamata fattoriale_ricorsivo(2):

**Figura 5:** Fattoriale: Restituzione del primo risultato

Successivamente, il risultato di fattoriale_ricorsivo(2) viene sostituito nella chiamata fattoriale_ricorsivo(3):

**Figura 6:** Fattoriale: Restituzione del secondo risultato

Infine, il risultato di fattoriale_ricorsivo(3), ossia 6, viene restituito alla funzione main:

**Figura 7:** Fattoriale: Restituzione risultato finale

Da notare che in questa seconda fase abbiamo risalito la catena delle chiamate, partendo dall'ultima chiamata effettuata. Questa seconda fase prende il nome di Unwind o Srotolamento:

**Figura 8:** Fattoriale: Fase di Pile Up e Fase di Unwind

Definizione

Pile Up e Unwind

Una chiamata ad una funzione ricorsiva si divide in due fasi:

Pile Up: le chiamate alla funzione si impilano una sopra l'altra fino a raggiungere il caso base.
Unwind: le chiamate vengono risolte una alla volta, partendo dall'ultima chiamata effettuata.

Tutto questo è possibile grazie alla presenza dello Stack di Chiamata che consente di memorizzare le chiamate alle funzioni in modo ordinato. Ogni chiamata ricorsiva, infatti, crea uno Stack Frame sullo stack che contiene i parametri e le variabili locali della funzione.

Fondamentale importanza riveste, in una funzione ricorsiva, il cosiddetto caso base. Il caso base è una condizione che, se verificata, interrompe la ricorsione. In assenza di un caso base, la funzione ricorsiva continuerebbe a chiamarsi all'infinito, causando un overflow dello stack. Infatti, ogni chiamata alla funzione ricorsiva consuma memoria sullo stack, e se non c'è un modo per interrompere la ricorsione, lo stack si riempirà fino a che non sarà più in grado di contenere nuove chiamate.

Nota

Mai dimenticare il caso base in una funzione ricorsiva

Il caso base di una funzione ricorsiva è quella condizione che interrompe la ricorsione.

La sua presenza non deve mai essere trascurata, altrimenti la funzione ricorsiva potrebbe continuare a chiamarsi all'infinito, causando un overflow dello stack.

Questo errore è l'equivalente ricorsivo di un ciclo infinito.

Uno schema generale, quindi, per una funzione ricorsiva è il seguente:

tipo_ritorno funzione(parametri) {
    if (caso_base) {
        /* Caso base */
        return valore;
    } else {
        /* Caso generale */
        return funzione(parametri);
    }
}

Esempio: Calcolo della Potenza

Proviamo a realizzare una funziona che calcola la potenza tra interi.

Una prima versione iterativa potrebbe essere scritta tenendo presente che la potenza di un numero con esponente intero può essere calcolata moltiplicando il numero per se stesso tante volte quante è l'esponente:

b ^ e = \underbrace{b \cdot b \cdot b \cdot \ldots \cdot b}_{e \text{ volte}}

Quindi possiamo scrivere la funzione in questo modo:

int potenza_iterativa(int base, int esponente) {
    int potenza = 1;
    for (int i = 0; i < esponente; i++) {
        potenza *= base;
    }
    return potenza;
}

In questo caso, la funzione potenza_iterativa calcola la potenza di un numero intero base elevato ad un altro numero intero esponente in modo iterativo, moltiplicando base per esponente volte usando un ciclo for.

Volendo realizzare la stessa funzione in modo ricorsivo, possiamo ridefinire la potenza in termini di se stessa:

b ^ e = \left\{ \begin{array}{ll} 1 &amp; \text{se } e = 0 \\ b \cdot b^{e-1} &amp; \text{altrimenti} \end{array} \right.

In questo caso, la funzione potenza_ricorsiva calcola la potenza di un numero intero base elevato ad un altro numero intero esponente in modo ricorsivo, moltiplicando base per la potenza di base con esponente esponente - 1.

int potenza_ricorsiva(int base, int esponente) {
    if (esponente == 0) {
        /* Caso base */
        return 1;
    } else {
        /* Caso generale */
        return base * potenza_ricorsiva(base, esponente - 1);
    }
}

Provando a richiamare la funzione potenza_ricorsiva con i parametri 2 e 3, otterremmo il seguente schema di chiamata:

**Figura 9:** Potenza: Catena di chiamate Ricorsiva

Esempio: La Sequenza di Fibonacci

La Sequenza di Fibonacci è una particolare sequenza numerica di interi:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots

Questa sequenza inizia per 0 e 1 ed ha la peculiarità che ogni elemento successivo è la somma dei due elementi precedenti.

La sequenza di Fibonacci appare spesso in natura e in matematica, ed è stata studiata fin dall'antichità. Essa descrive, ad esempio, la struttura di una spirale. All'infinito, il rapporto tra due elementi successivi tende al valore costante di:

\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618033988749895

Che prende il nome di Rapporto Aureo.

La successione di Fibonacci può essere definita in modo ricorsivo come segue:

F(n) = \left\{ \begin{array}{ll} 0 &amp; \text{se } n = 0 \\ 1 &amp; \text{se } n = 1 \\ F(n-1) + F(n-2) &amp; \text{altrimenti} \end{array} \right.

Proviamo ad implementare un programma in C che prende in ingresso un numero intero n e restituisce l'n-esimo elemento della sequenza di Fibonacci.

#include <stdio.h>

/* Prototipo della funzione */
unsigned long long int fibonacci(unsigned int n);

int main() {
    /* Input dell'utente */
    unsigned int n;

    /* Richiesta del numero all'utente */
    printf("Inserisci un numero intero: ");
    scanf("%u", &n);

    /* Calcolo e stampa del risultato */
    printf("L'elemento %u della sequenza di Fibonacci è %llu\n", n, fibonacci(n));
    return 0;
}

/* Definizione della funzione */
unsigned long long int fibonacci(unsigned int n) {
    if (n == 0 || n == 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Provando a compilare ed eseguire il programma, alcuni esempi di output potrebbero essere:

Inserisci un numero intero: 0
L'elemento 0 della sequenza di Fibonacci è 0

Inserisci un numero intero: 5
L'elemento 5 della sequenza di Fibonacci è 5

Inserisci un numero intero: 10
L'elemento 10 della sequenza di Fibonacci è 55

Inserisci un numero intero: 40
L'elemento 40 della sequenza di Fibonacci è 102334155

Il programma invoca la funzione fibonacci per ottenere il risultato. La funzione, dapprima controlla il caso base, poi calcola il risultato come la somma dei due elementi precedenti. Per far questo, essa invoca per ben due volte se stessa.

La riga 24, infatti, contiene la seguente istruzione:

return fibonacci(n - 1) + fibonacci(n - 2);

Questa istruzione invoca la funzione fibonacci due volte, una volta con il parametro n - 1 e una volta con il parametro n - 2. Questo è possibile grazie alla ricorsione.

Volendo rappresentare la catena delle chiamate alla funzione fibonacci per n = 3, la fase di Pile Up è la seguente:

**Figura 10:** Fibonacci: Fase di Pile Up

Analogamente a quanto visto per la funzione fattoriale, la fase di Unwind avviene quando si raggiunge il caso base. In questo caso il fondo della catena di chiamate è composto da più chiamate. Per cui la fase di Unwind avviene come mostrato in figura:

**Figura 11:** Fibonacci: Fase di Unwind

Ordine di valutazione delle Funzioni Ricorsive

La funzione per il calcolo dei numeri di Fibonacci presenta la stessa problematica che abbiamo affrontato quando abbiamo studiato le funzioni pure, impure e gli effetti collaterali.

Prendiamo la funzione fibonacci. Quando invochiamo la funzione con il parametro n = 3:

fibonacci(3);

Questa invocazione si traduce in:

return fibonacci(2) + fibonacci(1);

Ma in questo caso, quale operando viene valutato per primo? fibonacci(2) o fibonacci(1)?

Lo standard del C non lo specifica. Si potrebbe pensare che la chiamata a fibonacci(1) venga effettuata prima di fibonacci(2), assumendo che l'ordine sia da sinistra a destra. Tuttavia, il compilatore per ottimizzare il codice eseguibile potrebbe scegliere di invocare fibonacci(2) prima di fibonacci(1). Quindi non bisogna fare assunzioni sull'ordine di valutazione degli operandi.

In questo caso, valutare prima fibonacci(1) o fibonacci(2) non cambia il risultato finale, in quanto fibonacci è a tutti gli effetti una funzione pura. Per cui, l'ordine di valutazione degli operandi non è rilevante.

Ci sono casi, però, in cui le funzioni potrebbero, al proprio interno, modificare variabili globali o avere effetti collaterali. In questi casi, l'ordine di valutazione degli operandi potrebbe essere rilevante.

In generale, con le funzioni ricorsive è sempre consigliabile evitare effetti collaterali ed utilizzare solo funzioni pure.

Complessità Esponenziale

Un problema delle funzioni ricorsive è che possono portare a problemi di prestazioni e di memoria, se non utilizzate correttamente.

Ritorniamo al caso della funzione fibonacci:

unsigned long long int fibonacci(unsigned int n) {
    if (n == 0 || n == 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

Ciascun livello della ricorsione, infatti, comporta ben due chiamate ricorsive. Questo significa che il numero di chiamate raddoppia ad ogni livello.

Se vogliamo calcolare il numero n-esimo della sequenza di Fibonacci, il numero di chiamate alla funzione fibonacci sarà $2^n$ .

Questo potrebbe rapidamente portare a situazioni in cui il numero di chiamate esplode in maniera esponenziale. Ad esempio, per calcolare il numero 20 della sequenza di Fibonacci, la funzione fibonacci verrà chiamata $2^{20} = 1.048.576$ volte, poco più di un milione di volte!. Per calcolare il numero 30, la funzione verrà chiamata $2^{30} = 1.073.741.824$ volte, più di un miliardo di volte!.

Possiamo immaginare la drammaticità di questa situazione se consideriamo che ogni chiamata alla funzione fibonacci consuma memoria sullo stack. Se il numero di chiamate cresce in maniera esponenziale, lo stack si riempirà rapidamente, causando un overflow dello stack.

Nel gergo degli algoritmi, soluzioni di questo tipo hanno una Complessità Esponenziale e vanno evitati laddove possibile.

Nel caso della serie di Fibonacci, possiamo implementare la funzione in modo iterativo in questo modo:

unsigned long long int fibonacci_iterativo(unsigned int n) {
    unsigned long long int a = 0, b = 1, c;
    if (n == 0) {
        return a;
    }
    for (unsigned int i = 2; i <= n; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

In questo caso, la funzione fibonacci_iterativo calcola il numero n-esimo della sequenza di Fibonacci in modo iterativo, utilizzando due variabili a e b per memorizzare i due numeri precedenti.

Nota

Rischio di Complessità Esponenziale

Quando si adoperano funzioni ricorsive si può incappare facilmente in casi in cui lo Stack di Chiamata viene sovraccaricato. Questo accade quando il numero di chiamate alla funzione cresce in maniera esponenziale.

In tali casi conviene evitare la ricorsione e adottare una soluzione iterativa.

Ricorsione vs Iterazione

La ricorsione è un concetto molto potente e flessibile, che permette di risolvere problemi complessi in modo elegante e conciso. Tuttavia, la ricorsione non è sempre la soluzione migliore. Spesso, una soluzione iterativa, che fa uso di cicli while, for e do-while, è più efficiente e più veloce di una soluzione ricorsiva.

Confrontiamo i due approcci:

Sia l'approccio iterativo che quello ricorsivo fanno uso di istruzioni di controllo del flusso:

L'iterazione fa uso di cicli while, for e do-while per ripetere un blocco di istruzioni un numero finito di volte.

La ricorsione si affida, invece, ad un'istruzione if per interrompere la ricorsione oppure continuarla.
Entrambe usano meccanismi per ripetere un blocco di istruzioni:

L'iterazione ripete un blocco di istruzioni finché una condizione è vera.

La ricorsione ripete un blocco di istruzioni chiamando se stessa.
Entrambe usano dei meccanismi per interrompere la ripetizione:

L'iterazione interrompe la ripetizione quando la condizione del ciclo non è più vera.

La ricorsione interrompe la ripetizione quando viene raggiunto il caso base.
Sia un'iterazione che una ricorsione possono, in caso di errata implementazione, portare a cicli infiniti:

Un ciclo while o for mal implementato potrebbe non terminare mai.

Una funzione ricorsiva mal implementata potrebbe chiamarsi all'infinito.

La ricorsione ha vari aspetti negativi. Il principale è che essa utilizza ripetutamente il meccanismo di invocazione di una funzione. Invocare una funzione ha comunque un costo sia in termini di tempo che di memoria.

Infatti, ogni chiamata ricorsiva consuma memoria sullo stack, in quanto deve creare uno stack frame dove verranno salvate le variabili locali e i parametri della funzione.

L'iterazione, viceversa, non ha questo problema. Un ciclo for o while non crea stack frame e non consuma memoria sullo stack ma riutilizza sempre le stesse variabili. Il costo di chiamare una funzione non è presente.

Detto questo allora perché usare la ricorsione?

La verità è che qualunque algoritmo iterativo può essere implementato in maniera ricorsiva e viceversa. L'approccio ricorsivo viene scelto quando la ricorsione rispecchia la natura matematica stessa del problema generando, quindi, programmi più semplici da leggere e su cui è più semplice effettuare il debug.

Inoltre, come risulta evidente dal caso della Serie di Fibonacci, una soluzione iterativa non sempre è immediata. In parole povere, la ricorsione è, spesso, la soluzione più semplice e naturale.

Esiste, tuttavia, una tecnica che unisce il meglio di entrambi gli approcci: la Ricorsione in Coda o Tail Recursion. Vedremo questa tecnica nelle prossime lezioni.

In Sintesi

In questa lezione abbiamo visto che:

Una funzione può chiamare se stessa; questo meccanismo è chiamato ricorsione;
una funzione ricorsiva è una funzione definita in termini di se stessa;
la ricorsione può portare a problemi di prestazioni e di memoria, se non utilizzata correttamente;
la ricorsione può essere sostituita da un'iterazione e viceversa;
una chiamata a funzione ricorsiva può essere rappresentata come una catena di chiamate e si divide in due fasi: Pile Up e Unwind;
una funzione ricorsiva può avere una complessità esponenziale mentre una funzione iterativa no;
la ricorsione è un concetto molto potente e flessibile, ma non sempre è la soluzione migliore;

Inoltre, abbiamo visto come implementare funzioni ricorsive per il calcolo del fattoriale, della potenza e della serie di Fibonacci.

Lezione Precedente Indice del capitolo