La ricorsione è una tecnica di programmazione, che sfrutta l’idea di suddividere un problema da risolvere in sottoproblemi simili a quello originale, ma più semplici. Un esempio è l’elevamento a potenza, infatti si avrà:
xn = x * xn-1. Ma se n = 0 allora x0 = 1. Pertanto avremo la seguente funzione ricorsiva all’interno del programma:
Altri esempi sono dati dai seguenti esercizi
1.Scrivere una funzione che calcoli il fattoriale di un numero
2.Scrivere una funzione ricorsiva che calcoli, ricorsivamente, la somma di tutti i numeri compresi tra 0 ed x
3.Si scrivano le versioni ricorsiva di una funzione: f(a,n); che calcoli il seguente valore
4.Scrivere una funzione ricorsiva (in C) che calcoli la somma degli elementi di un array a[1..n] di n ≥ 1 interi
| Soluzione 1. int fatt(int n) { if (n>1) return n*fatt(n-1); else return 1; } |
| Soluzione 2. int somma(int x) { if (x == 0) return 0; else return x + somma(x-1); |
| Soluzione 3. float f(float a, int n) { if (n==1) return a – 1/a; else return a – n/a + f(a, n-1); } |
| Soluzione 4. int somma(int a[]; int n) { if (n==0) return 0; else return a[n] + somma(a, n-1); } |