Una funzione ricorsiva è una funzione che richiama se stessa direttamente o indirettamente attraverso un’altra funzione .
La ritorsione è un argomento molto complesso e molto discusso nell’ambito dell’informatica.
In primo luogo consideriamo la ricorsione dal punto di vista concettuale .
Gli approcci ricorsivi alla soluzione dei problemi hanno un certo numero di elementi in comune.
La funzione ricorsiva sa come risolvere soltanto come risolvere il caso più semplice del problema anche detto caso base!!.
Nel caso invece la funzione venga invocata su un problema più complesso, lo dividerà in due parti ,una che la funzione sa come risolvere un ‘altra che non sa come risolvere.
Per rendere fattibile la ritorsione,la seconda parte dovrà somigliare alla prima,ma dovrà essere anche una versione leggermente più semplice.
Dato che questo nuovo problema somiglierà all’originale , la funzione invocherà una nuova copia di se stessa perché lavori sul problema più piccolo questo fase viene detta chiamata ricorsiva.
la chiamata ricorsiva includerà anche la parola chiava return perché il suo risultato sarà combinato con la porzione del problema che la funzione sa risolvere.
La chiamata ricorsiva sarà eseguito fintanto che la chiamata originata della funzione sarà ancora aperta.
la chiamata ricorsiva potrà generare molte altre chiamate ricorsive simili.
Perché la ritorsione possa terminare,ogni volta che la funzione richiamerà se stessa con una versione leggermente semplificata del problema dovrà convergere alla fine a un caso base.
A quel punto la funzione riconoscerà il caso base ,restituirà un risultato sulla copia precedente e ne conseguirà una sequenza di restituzioni lungo tutta la catena di chiamate finchè quella della funzione originaria non restituirà direttamente al main il risultato finale
Esempio calcolo del fattoriale :
[code lang=”objc”]
#include <stdio.h>
long fattoriale(long num);
&nbsp;
int main ()
{
int i;
for (i=0; i<=10; i++) {//itera 11 a ogni iterazione calcola il fattoriale
printf("%2d!= %ld\n",i,fattoriale(i));
}
return 0;
}
&nbsp;
//funzione ricorsiva per il calcolo del fattoriale
long fattoriale(long num){
if (num<=1) {//caso vase
return 1;
}
else{//passo ricorsivo
return (num*fattoriale(num-1));
}
}
[/code]
Output
0!= 1
1!= 1
2!= 2
3!= 6
4!= 24
5!= 120
6!= 720
7!= 5040
8!= 40320
9!= 362880
10!= 3628800
Ora vedremo un nuovo esempio scriveremo un programma ricorsivo sulla serie di numeri di Fibonacci
La serie di F. è la seguente:
0,1,1,2,3,5,8,13,21…..
Comincia con 0 e 1 e gode della proprietà che ogni suseguente numero di Fibonacci è la somma dei due numeri che lo precedono.
La serie di Fibonacci può essere definita in modo ricorsivo in questo modo :
fibonacci(0)=0
fibonacci(1)=1
fibonacci(n)=fibonacci(n-1)+(fibonacci(n-2)
ESEMPIO
[code lang=”objc”]
&nbsp;
#include <stdio.h>
long fibonacci (long n);
int main ()
{
long risul;//valore di fibo
long num;//numero da calcolare
printf("Inserisci un intero");
scanf("%d",&num);
risul=fibonacci(num);
&nbsp;
return 0;
}
long fibonacci (long n){
if (n==0||n==1) {//caso base
return n;
}
else{
return fibonacci(n-1)+fibonacci(n-2);//chiamata ricorsiva
}
}
[/code]