Analisis de los algoritmos recursivo e iterativo para la serie fibonacci

DIFERENCIA ENTRE ITERACION Y RECIRSIVIDAD

• Un algoritmo recursivo es un algoritmo que expresa la solución de un problema en términos de una llamada a sí mismo. La llamada a sí mismo se conoce como llamada recursiva o recurrente.
• Iteración es la repetición de una serie de instrucciones en un programa de computadora.

CODIGO FIBONACCI RECURSIVO

#include<stdio.h>
#include<stdlib.h>

int n,o,fib; //Declaracion de variables
int fibon(int n); //Declaracion de funcion

int main()
{
    do
    {
      system("cls");
      printf("Proporciona el elemento de la serie fibonacci que deseas generar: ");
      scanf("%d", &n);
      fib=fibon(n);              //Se llama a la funcion fibon
      printf("\nElemento: %d \tValor: %d", n, fib);
      printf("\n\nDesea buscar otro elemnto (si-1, no-2): ");
      scanf("%d", &o);
    }while(o==1);
    return 0;
}
int fibon(int n)
{
     if(n<=1)
             return (n);
     else
         return(fibon(n-1)+fibon(n-2));
}

CODIGO FIBONACCI ITERATIVO

#include<stdio.h>
#include<stdlib.h>

main()
{
    int a=0,b=1,c,i,n,o;  //Declaracion de variables
     
    do
    {
      system("cls");
      printf("Proporciona el elemento de la serie fibonacci que deseas generar: ");
      scanf("%d", &n);
      for(i=0;i<n-1;i++)
      {
          c=a+b;
          a=b;
          b=c;
      }
      printf("\nElemento: %d \tValor: %li", n, c);
      printf("\n\nDesea buscar otro elemnto (si-1, no-2): ");
      scanf("%d", &o);
    }while(o==1);
}

RESULTADOS

 

Como se muestra en la tabla anterior,en el algoritmo recursivo al principio no se notaba la diferencia en los tiempos pero a partir de los 40 elementos el intervalo en el tiempo tambien aumentaba y cada vez considerablemente, a tal grado que al intentar generar 55 elementos y esperar mas de 30 minutos aun no se obtenian resultados. En cambio en el algoritmo iterativo el tiempo se mantenia constate.

CONCLUSION

El modelo recursivo se basa en llamadas sucecivas a si mismo. Cada llamada ocupa un lugar en la pila. El problema es que para la sucesión de fibonacci se generan el doble de llamadas ya que por naturaleza del problema: para hallar el siguiente número se han de obtenerse los dos anteriores inmediatos. Para obtener a estos dos, se requiere una vez más de 2 llamadas (tal y como se muestra en la siguiente imagen). De modo que la pila puede desbordar con facilidad.

Por su parte la versión iterativa tiene un consumo constante de memoria, no emplea la pila. 

Si ha de obtenerse el n-ésimo número se requieren de n-pasadas por lo que su complejidad es linal: O(n), mientras que su contraparte recursiva es exponencial O(c^n). Así el más rápido es el iterativo.