Bene, suscitata una certa curiosità sull'argomento, vediamo cosa esse siano in realtà. Una funzione ricorsiva è una funzione che contiene al suo interno una chiamata a se stessa6.3. Perché? In determinati casi gli algoritmi ricorsivi (e quindi le funzioni ricorsive) sono meglio adatti a modellizzare un problema di quelli iterativi. Il classico esempio è la definizione stessa di fattoriale di un numero intero:
// ex6_3_2.cpp #include <iostream.h> int fattRicorsivo (int n) { if (n == 0) return 1; return n*fattRicorsivo (n - 1); } void main() { cout << "6! = " << fattRicorsivo(6); }
output:
6! = 720
Cosa succede quando all'interno di main
chiamiamo la funzione fattRicorsivo
? Viene chiamata la funzione seguente:
fattRicorsivo (6) |
6 == 0
, essa chiama la seguente funzione:
fattRicorsivo (5) |
fattRicorsivo (0) |
Come si può vedere si tratta di un procedimento molto lungo e tortuoso, che tuttavia in certi casi semplifica notevolmente la vita del programmatore, come vedremo tra poco. Prima però presentiamo due semplici esempi di programmi contenenti funzioni ricorsive:
// ex6_3_3 // calcola N termini della successione di Padovan #include <iostream.h> int padovan (int n) { if (n == 0 || n == 1 || n == 2) return 1; return padovan(n-2) + padovan(n-3); } void main() { const int N = 15; for (int i = 0; i < N; i++) if (i % 5 == 4) cout << padovan(i) << "\n"; else cout << padovan(i) << "\t"; }
output:
1 | 1 | 1 | 2 | 2 | |
3 | 4 | 5 | 7 | 9 | |
12 | 16 | 21 | 28 | 37 |
// ex6_3_4 // calcola l'n-esima potenza intera di un numero reale #include <iostream.h> double potRicorsiva (double base, int esponente) { if (esponente == 0) return 1; return base * potRicorsiva (base, esponente - 1); } void main() { double b; int e; cout << "base? "; cin >> b; cout << "esponente? "; cin >> e; cout << "risultato: " << potRicorsiva (b, e); }
esempio di output:
base? 1.331335
esponente? 4
risultato: 3.14159