Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 1
Ricorsione
Il concetto di ricorsione (o ricorsività) si riconduce a quello di induzione matematica
Principio di induzione
Sia P un predicato sull’insieme N dei numeri naturali e sia vero il predicato P(0); se per ogni k (con k N) dal predicato P(k) vero discende la verità di P(k+1), allora P(n) è vero per qualsiasi n .
Es.
Fattoriale di n
0! = 1
n! = n * (n-1)!
Un algoritmo ricorsivo può essere espresso mediante un sottoprogramma ricorsivo, cioè un sottoprogramma che chiama se stesso (ricorsione diretta).
Il predicato P(0) forma il cosidetto ‘caso base’
Un sottoprogramma è ricorsivo quando chiama se stesso, direttamente o indirettamente
Es.
Il fattoriale è un tipico esempio di algoritmo ricorsivo
n! = n * (n-1) * (n-2) * ... * n * 1 = n (n-1)!
5! = 5 * 4 ! = 5 * (4 * 3!) = 5 * (4 * (3 * 2!)) = 5 * (4 * (3 * (2 * 1!))) = 5 * (4 * (3 * (2 * (1 * 0!)))) 0! = 1 Caso base
Ricorsione
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 3
Ricorsione
Si innesca un ‘ciclo’ di attivazioni, non esplicitamente realizzato con strutture cicliche, dovuto alle susseguenti attivazioni che il sottoprogramma fa a se stesso (se il sottoprogramma richiama se stesso, questa chiamata a sua volta richiemerà di nuovo il sottoprogramma e così via).
A ciascuna attivazione del sottoprogramma corrisponde una nuova istanziazione delle sue variabili che contengono i valori correnti calcolati (questi sono mantenuti fino alla terminazione dell’esecuzione relativa alla corrispondente attivazione).
#include <stdio.h>
long fat(int);
main() {int n;
printf("CALCOLO DI n!\n\n");
printf("Inserire valore di n: \n");
scanf("%d", &n);
printf("Il fattoriale di: %d ha valore: %d\n", n, fat(n));
}
long fat(int n) {long a;
if (n==0) a=1;
else
a= n*fat(n-1);
return a;
Calcolo fattoriale con sottoprogramma ricorsivo
Soluzione iterativa:
……
if(n==0) fat = 1;
else fat=1;
for(fat=n; n>2; n--) fat = fat*(n-1);
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 5
Ricorsione
Esempio di esecuzione ricorsiva per il calcolo di 3!:
Bisogna assicurarsi che la ricorsione converga altrimenti si genera una ricorsione infinita !!
main
…….
fat(3);
……..
fatt(n)
…….
if (n==0) a=1;
else a=n*fat(n-1);
return a;
……..
fatt(n)
…….
if (n==0) a=1;
else a=n*fat(n-1);
return a;
……..
fatt(n)
…….
if (n==0) a=1;
else a=n*fat(n-1);
return a;
……..
1 2 3
fatt(n)
…….
if (n==0) a=1;
else a=n*fat(n-1);
return a;
……..
4
return a = 1 return a = 1
return a = 2 return a = 6
//n = 3 //n = 2 //n = 1 //n = 0
Calcolo fattoriale con sottoprogramma ricorsivo
… fare attenzione affinchè la ricorsione ‘converga’ , cioè non sia infinita
… valori ‘ritornati’ …
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 7
• Serie di Fibonacci : 0, 1, 1, 2, 3, 5, 8, 13, 21, ...
– Ogni numero è la somma dei due precedenti:
fib(n) = fib(n-1) + fib(n-2) formula ricorsiva
long fibonacci(long n) {
if (n==0 || n==1) // caso base a = n;
else a = fibonacci(n-1) + fibonacci(n-2);
return a;
}
Esempio: Serie di Fibonacci
#include <stdio.h>
long int fibo(int);
main(){
int n;
printf(“Serie di Fibonacci f(0)= 1 f(1)=1 f(n)=f(n-1)+f(n-2)");
printf("\nInserire n: \t");
scanf("%d", &n);
printf("Termine della serie di argomento %d: %d\n", n, fibo(n));
}
long int fibo(int n) {long int a;
if(n==0) a=0;
else
if(n==1) a = 1;
else
a =( fibo(n-1)+ fibo(n-2) );
Serie di Fibonacci
F(n) = F(n 1) + F(n 2) Per esempio
F(2) = 1 + 0 = 1 F(3) = 1 + 1 = 2 F(4) = 2 + 1 = 3 F(5) = 3 + 2 = 5 F(6) = 5 + 3 = 8 F(7) = 8 + 5 = 13
Elementi di Informatica
Prof. G. A. Di Lucca - Univ. del Sannio 9
f( 3 )
f( 1 ) f( 2 )
f( 1 ) f( 0 ) return 1
return 1 return 0
return +
+ return
Serie di Fibonacci
… attivazioni per n =3…
Ricorsione vs. Iterazione
• Ripetizione
– Iterazione: loop espressi esplicitamente
– Ricorsione: chiamate a sottoprogrammi ripetute (non esplicitamente)
• Terminazione
– Iterazione : controllate esplicitamente da condizioni – Recursion: riconoscimento del caso base
• Possibilità /Rischio di avere per entrambe ripetizioni infinite
• Algoritmi iterativi sono più performanti; algoritmi ricorsivi sono più comprensibili (migliore ingegnerizzazione del sw)
