Prima di proseguire...
Potrebbe interessarti la nostra collezione di esercizi C risolti?
Vediamo oggi gli svantaggi dell’uso delle funzioni ricorsive, con un tipico esempio di funzione ricorsiva : la successione di Fibonacci.
Per chi non si ricordasse che cosa è la successione di Fibonacci : è una successione che ha come primi due numeri 0 ed 1 e poi gli altri si ricavano sommando i due numeri precedenti.
esempio:
0, 1, 1, 2, 3, 5, 8, …
Un grosso svantaggio delle funzioni ricorsive è legato alla velocità di esecuzione.
L’unico loro vantaggio sta nel fatto che alcuni algoritmi sono più facili da realizzare in modo ricorsivo(ad esempio la sequenza di Fibonacci, il fattoriale, ecc).
Abbiamo provato a calcolare il 40° numero della sequenza di Fibonacci con un algoritmo ricorsivo e uno iterativo ed i risultati sono stati i seguenti:
Algoritmo ricorsiva : 3.300 s
Algoritmo iterativa : < 0.000s
Come si può vedere la "vittoria" degli algoritmi iterativi è schiacciante.
Quindi quando potete usate sempre gli algoritmi iterativi, cercando di trasformare algoritmi ricorsive in iterative.
A scopo informativo vengono allegati i vari programmi utilizzati :
ricorsivo:
[c]
#include<stdio.h>
int fibonacci(int num);
int main(){
//dichiarazioni
int num;
//acquisizioni
do{
printf("inserire il numero(>=0) della sequenza di fibonacci da visualizzare : ");
scanf("%d",&num);
}while(num<0);
//stampa
printf("%d\n",fibonacci(num));
}
int fibonacci(int num){
if(num<=1)
return num;
return (fibonacci(num-1)+fibonacci(num-2));
}
[/c]
Iterativo:
[c]
#include<stdio.h>
int fibonacci(int num);
int main(){
//dichiarazioni
int n;
//acquisizione dati
do{
printf("inserire il numero di termini da visualizzare : ");
scanf("%d",&n);
}while(n<0);
//calcoli e visualizzazione risultati
printf("%d\n",fibonacci(n));
}
int fibonacci(int num){
int i,a=0,b=1;
if(num==0)
return 0;
for(i=1;i<num;i++){
b += a;
a = b - a;
}
return b;
}
[/c]
perché non usare le funzioni ricorsive? (esempio fibonacci) by cardinale claudio is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.