14 jul. 2011

Fibonacci recursivo - Mala idea

Algoritmos Computacionales 

Ya sabemos que hacer Fibonacci en lenguaje C esta muy repetitivo, pero ahora vengo a intentar mostrarles el porque es muy mala idea querer hacer la serie en forma recursiva.

En la siguiente imagen muestro el código para la serie de Fibonacci en forma recursiva. Lo que he agregado es un contador dentro de la función "fibo" para conocer al final cuantas veces se manda a llamar y así tener un punto de comparación con la forma iterativa.


También en la forma iterativa agregue un contador, que en realidad no se necesitaba por el hecho de ser iterativo, pero lo pongo al igual que en recursivo para conocer las veces que se repite el proceso.


Los resultados son los siguientes:


Tenemos que Fibonacci recursivo con una instancia de 40, el contador nos da como resultado 331160281, esto quiere decir que se hace tal cantidad de llamadas.

En cambio con forma iterativa:


Tenemos que solamente se repite el proceso 39 veces para una instancia de 40.

Para esta demostración tomamos la instancia como la cantidad de números de la serie de Fibonacci que se desean obtener.

En cuanto a tiempo de ejecución también nos da en la forma recursiva, un tiempo mayor, esto se podría verificar colocando un contador de tiempo.

Conclusión:
Es muy mala idea hacer la serie de Fibonacci con fines prácticos.

1 comentario: