martes, 12 de octubre de 2010

.: ¿Fibonacci en Recursivo? :.

:: El Drama de Fibonacci ::



Materia. Lab de Leng de Progr

Hora. V1(Jueves)

Si nos ponemos a pensar un poco, la recursividad tiene la ventaja de que es muy útil al momento de querer solucionar problemas muy complejos de manera iterativa. Sin embargo, tenemos una gran desventaja: la ineficiencia del programa.

Por ejemplo, tenemos el caso del programa de la factorial de un número. Tenemos el problema de la cantidad de memoria que puede llevarse todo el proceso recursivo, un posible desbordamiento de pila, entre otros.

El caso que tiene riesgos, quizás los mismos que el de la factorial, pero un poco más elevados, es hacer la serie de Fibonacci en código recursivo.

El caso base no tiene gran problema; sin embargo, el problema entra cuando se ejecuta la recursividad, pues cada vez que se hace una llamada a sí misma, lo hace por dos veces. Esto viene generando el doble de ineficiencia y el doble riesgo de un desbordamiento (sino es que hasta más).

Para que lo visualicen más, piensen en el proceso con “n = 6”. Haciendo una representación en tipo árbol binario, tendríamos algo como esto:



Si se dan cuenta, para n = 6, tiene que calcular la misma función para n = 5 y luego sumarle el resultado de la misma con n = 4. Y lo malo es que para cada uno de éstos, tenemos otros dos procesos.

Hay que pensar en lo que hace el procesador y la memoria RAM con todo esto si metemos números realmente grandes.

Es casos como estos, tenemos que apiadarnos de nuestro equipo. Por lo tanto, convendría más el proceso iterativo.

En el caso de Fibonacci, tendríamos el código así (para imprimir los primeros 20 números, claro:

#include <stdio.h>

int main(void){
    int i, a = 1, b = 0, c = 0;

    for(i = 1; i <= 20; i++){
        printf("\n%d). %d",i,c);

        c = a + b;
        a = b;
        b = c;
    }

    return 0;
}

Como pueden ver, este código resulta mucho más eficiente que el recursivo.

Cualquier duda y/o comentario, no duden en mencionarlo.

Saludos.

Fuente: http://latecladeescape.com/w0/basico/entender-la-recursividad/el-drama-de-fibonacci.html

1 comentario: