jueves, 13 de marzo de 2014

Algoritmos: Recursivos vs Iterativos

Algoritmos
Recursivos vs Iterativos

En esta entrada, veremos, en lenguaje de programación C++, diferencias y ejemplos entre estos dos tipos de algoritmos: Los algoritmos recursivos, y los algoritmos iterativos.



Veremos esto tomando como ejemplo la Sucesión de Fibonacci (0,1,1,2,3,5,8...).
Para hayar un término n de la sucesión, tenemos esta función:

F(n)=
  • 0                    si n = 0
  • 1                    si n = 1
  • F(n-1)+F(n-2)   si n > 1

En resumen: cada término, es la suma de los dos anteriores. Salvo el término 0 y el 1, que son 0 y 1, respectivamente.

Una función recursiva, es la que se llama a si misma. Para que una función recursiva tenga fin, ha de tener una condición, como en este ejemplo: "si n=0" o "si n=1".

Veamos la función Fibonacci recursiva en C++:


uint64_t fib_recursivo(uint64_t n){
    if(n==0) return 0;
    if(n==1) return 1;
    return fib_recursivo(n-1) + fib_recursivo(n-2);
}

PD: uint64_t es lo mismo que unsigned long long int.

En esta sencilla función, vemos claramente la definición de la serie de Fibonacci. N es el término de la serie que queremos conseguir.

Ahora veamos la forma iterativa:


uint64_t fib_iterativo(uint64_t n){
    if(n==0) return 0;
    if(n==1) return 1;
    uint64_t a=0, b=1, c=0;;
    for(int i=2; i<=n; i++){
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

En la iterativa, vamos generando los términos en orden hasta llegar al que buscamos. en la variable 'a', guardamos lo que sería f(n-2), y en 'b', f(n-1). Luego, con el ciclo, igualamos 'c' a 'a' + 'b' ( f(n-2) + f(n-1) ).

Entre los algoritmos iterativos y los recursivos, suele haber estas diferencias básicas:

  1. La forma recursiva, es mucho más lenta que la forma iterativa, especialmente para números "grandes" (Ej. Para N=100, fib_recursivo() tardará mucho en terminar)
  2. La forma recursiva suele ser más sencilla de realizar que la iterativa. Aunque esto depende de la sucesión/algoritmo que busquemos.
A parte, os muestro otra función, parecida a la iterativa, pero con algunos cambios:


uint64_t fib_mezcla(uint64_t n){
    static vector<uint64_t> v;
    if(!v.size()){
        v.push_back(0);
        v.push_back(1);
    }
    if(v.size()<=n)
        for(uint64_t i=v.size(); i<=n; i++)
            v.push_back(v[i-1] + v[i-2]);
    return v[n];
}

Esta, lo que hace es guardar los valores que obtiene (por el método iterativo) en un vector static.
Al ser una variable static, no será borrada al acabar la función, lo que significa que guardará los valores que tiene cada vez q llamemos a la función. De esta manera, ahorramos tiempo, ya que no tenemos que calcular (salvo la primera vez), cada término de fibbonaci. A cambio, tiene un mayor gasto de memoria. Pero en este caso, dado que apenas guardará más de 87 términos (a partir de ahí se sale del tamaño de una variable de 64 bits), apenas notaremos su gasto de memoria.

Aquí he hecho unas pruebas comparativas de las 3 funciones:


En la primera prueba, se mide el tiempo que tarda en llamar 1 vez a la función para el término 40. Como podemos observar, el método recursivo tarda más de 4 segundos, mientras que los demás, apenas tardan unos milisegundos.
En la segunda prueba, omito la función recursiva, ya que tardaría un tiempo o años en acabar. Aquí podemos ver lo que tardan los otros métodos al ser llamados 1.000.000 veces, para el término 85. Aquí es donde podremos apreciar la diferencia entre el método iterativo tradicional, y el método donde se guardan los valores. El método iterativo, se llama 1.000.000 veces, y las 999.999 veces hace todo el ciclo desde el 1 hasta el 85. En cambio, el otro método hace solo 1 vez el ciclo, y las otras 999.999 veces, simplemente retorna el valor guardado en el vector.

Y hasta aquí este resumen sobre los pros y contras de las funciones recursivas e iterativas. En vuestros programas, os recomiendo poner un límite para las funciones recursivas que podrían tardar mucho, como la de fibonacci, para así evitar que el programa se detenga.

No hay comentarios:

Publicar un comentario