Recursividad vs Iteración

Aspectos que hay que considerar al decidir cómo implementar la solución a un problema si es de forma iterativa o de forma recursiva:

• La carga computacional (tiempo de CPU y espacio en memoria) asociada a las llamadas recursivas.
• La redundancia (algunas soluciones recursivas resuelven un problema en repetidas ocasiones).
• La complejidad de la solución (en ocasiones, la solución iterativa es muy difícil de encontrar).
• La concisión, legibilidad y elegancia del código resultante de la solución recursiva del problema.

Algo recursivo o recurrente es algo que se llama a si mismo. Tiene que ver con el principio de inducción.

La recursividad consume muchísima memoria, ya que mantiene las variables del método mientras que se ejecuta, y también mucho tiempo. La recursividad es costosa pero es más natural, se prefiere. Por ejemplo, Java no puede implementar de forma recursiva el cálculo del factorial de un millón, pues cualquier computador se quedaría sin memoria, sin embargo, es necesario de implementar para poder escribir y entender ciertos programas.

Recursividad vs. Iteración

1- Ambas realizan una repetición:

a)Solución iterativa repite el cuerpo del bucle.

b)Solución recursiva repite las llamadas al método recursivo.

2- Ambas tienen una condición de terminación.

a)Solución iterativa: termina cuando se imcumple la condición de continuación del bucle.

b)Solución recursiva: se termina cuando una llamada alcanza el caso base (inducción) desencadenando una secuencia de vuelta atrás.

Backtracking: sucesión de pruebas tentativas.

3- Ambas se deben diseñar para converger a la solución (principio de convergencia, y que no se salten la condición de terminación).

a)Solución iterativa: se llega a cumplir la condición de terminación (esto se debe garantizar).

b)Solución recursiva: se debe garantizar que se llegue al caso base.

Principio importante: Toda solución recursiva puede encontrar una solución iterativa equivalente, mientras que lo contrario no siempre es cierto.

Ejemplo: Programa que calcula el factorial de un número

El código del programa que calcula el factorial es el siguiente:

FUNCION RECURSIVA

#include<iostream>

#include<iomanip>

long factorial(long);

int main(){

int num;

  cout<<"Entre el numero: ";

  cin>>num;

for(int i=0; i<=num; i++)

cout <<setw(2)<<i<<"!="

     <<factorial(i)

     << endl;

return 0;}

//Definicion Recursiva de la //Funcion Factorial

long factorial (long num){

if (number<=1)

 return 1;

else

 return num*factorial(num-1);}

// Obsérvese como la función se

// Llama así misma

FUNCION ITERATIVA

#include<iostream.h>

long factorial(long);

int main()

{

int num, fact;

cout<<"Entre un número ";

cin>>num;

resultado=factorial(num);

cout<<"El factorial es:"<<fact

    <<endl;

      return 0;}

long factorial(long num1)

{

int var=1;

int n=1;

 while(n<=num1){

   var=var*n;

   n++;

       }

  return var;

}

En conclusión la diferencia que podemos encontrar en la función recursiva y la iterativa es que la recursiva tienes que hacer constantes llamadas en las funciones que tienes en tu algoritmo o programa, mientras que en la iterativa no son necesarias tantas llamadas para la solución del problema.

Fuentes: http://elvex.ugr.es/decsai/c/apuntes/recursividad.pdf
http://shiman.wordpress.com/2008/05/28/recursion-vs-iteration/