Le funzioni ricorsive in C
Nel linguaggio C la ricorsione è una funzione che richiama se stessa
A cosa serve la ricorsione?
Spesso la ricorsione mi permette di ottenere un calcolo in modo più compatto, con un minore numero di righe di codice sorgente.
La ricorsione ha pro e contro
E' sicuramente una tecnica elegante di programmazione.
Tuttavia bisogna però fare attenzione al numero di ricorsioni, perché a ogni ricorsione la funzione alloca più memoria per salvare le nuove variabili locali.
Nota. Il concetto di funzione ricorsiva deriva dalla matematica (ricorsione matematica). E' usato in gran parte dei linguaggi di programmazione, non solo nel linguaggio C. Ecco un esempio di ricorsione in Python.
Un esempio pratico
Questo codice sorgente calcola il fattoriale n! di un numero tramite la ricorsione.
- #include <stdio.h>
- int fattoriale(int n) {
- if (n<2) {
- return 1;
- } else {
- return n*fattoriale(n-1);
- }
- }
- int main()
- {
- int numero=4;
- printf("Il fattoriale di %d è %d ", numero, fattoriale(numero));
- return 0;
- }
Nelle righe 2-8 definisco la funzione fattoriale() che riceve in ingresso un numero intero (n).
- Se il numero n è maggiore di uno, la funzione richiama se stessa passando in ingresso il numero intero n decrementato di uno (n-1).
- Se il numero n è uguale a uno, la funzione restituisce 1. La ricorsione si chiude moltiplicando tra loro tutti i risultati.
In questo caso chiamo la funzione fattoriale con il numero n=4 (righe 11-12).
Quindi l'output del programma è
Il fattoriale di 4 è 24.
Il fattoriale 4! in matematica è il prodotto 4·3·2·1 = 24
Vale la pena spiegare come funziona la ricorsione nel programma.
La funzione compie 3 ricorsioni ossia chiama se stessa tre volte.
fattoriale(4)=4*fattoriale(3)
fattoriale(3)=3*fattoriale(2)
fattoriale(2)=2*fattoriale(1)
La prima chiamata è fattoriale(4) che chiama 4*fattoriale(3) che, a sua volta, chiama 3*fattoriale(2). E via dicendo fino alla chiamata fattoriale(1).
Alla chiamata fattoriale(1) la funzione restituisce 1.
fattoriale(4)=4*fattoriale(3)
fattoriale(3)=3*fattoriale(2)
fattoriale(2)=2*1
Quindi fattoriale(2)=2
fattoriale(4)=4*fattoriale(3)
fattoriale(3)=3*2
Quindi fattoriale(3) è uguale a 6
fattoriale(4)=4*6
Pertanto, il fattoriale di n=4 è uguale a 24.
Nota. A ogni ricorsione il programma alloca altri indirizzi di memoria aggiuntivi per memorizzare i valori della variabile locale (n=3, n=2, n=1). Soltanto con la chiusura dell'ultima ricorsione fattoriale(1) comincia a liberare la memoria.
E così via.