Algunos podrán ver en la parte de arriba de mi blog una frase que dice: “La iteración es humana; la recursión, divina. L. Peter Deutsch.” Aun recuerdo el momento de mi vida como programador cuando aprendí a usar “recursión”, fue como haber descubierto, para mi, el Santo Grial de la programación, era un mundo nuevo y desconocido al que me estaba adentrando, pero como a Spiderman, “el tener un gran poder conllevaba una gran responsabilidad“, y por que digo esto, por que una vez que lo aprendí, todo los problemas los quería resolver recursivamente, y pues al tiempo aprendí que no, no todos se podían resolver de esta manera, y que no todas las recursiónes eran las soluciones mas optimas a un problema.

Pero, para los que no sepan, ¿que es recursión?

Según  Wikipedia(amo las definiciones de Wikipedia): Recurrencia, recursión o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente circulo sin fin en esta definición: Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

La recursividad no es propia de la programación, se puede ver en muchas partes, como el ejemplo de Wikipedia del  anuncio de cacao con una imagen recursiva. La mujer muestra un paquete idéntico al del propio anuncio, conteniendo así a otra mujer que muestra otro paquete más pequeño, de forma recursiva.

Propiedad de Wikipedia

Pero en términos informáticos, 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.

Iteración : es la repetición de una serie de instrucciones en un programa de computadora.

Y si leemos esta definición nos preguntaremos, ¿las dos son repeticiones, entonces, cual es la diferencia? Pues radica en que los algoritmos iterativos realizan ciclos, y se detienen cuando una condición se cumple, esta puede ser boleana, y los algoritmos recursivos hacen llamadas a si mismos.

Que debemos tomar en cuenta para saber que debemos de implementar a la hora de estar programando:

Nuestras capacidades técnicas, las características del ordenador que tenemos, la carga que va a recibir el mismo, la clase de datos que se van a procesar, la cantidad, si no caemos en metodos redundantes(que se resuelva varias veces un problema, por culpa de la recursividad), si realmente nos va a llevar a obtener la solución mas optima del mismo.  La realidad es que la recursión tiene un gran defecto, y es el hecho de consumir mucha memoria, puesto que se mantienen almacenadas las variables en un estado de ejecución.

Yo en lo personal la mayoría de veces uso los métodos recursivos, por supuesto, previo a un análisis de la solución mas optima.

Un ejemplo claro de Recursión Vs Iteración son las Torres de Hanoi resueltas mediante los dos metodos:
Recursivo

#include <stdio.h>
 static void hanoi(int ,int,int,int);
 main()
 {
    int x;
    printf("Numero de Discos\n");
    scanf("%d",&x);
    hanoi(x,1,2,3);
    }
 static void hanoi(int n,int inic,int temp,int fin)
 {
    if(n==1){
       hanoi(n-1,inic,temp,inic);
       printf("Movemos Disco de la Estaca %d a la Estaca %d\n",inic,fin);
    }
       if(n>1)
    {
       hanoi(n-1,inic,fin,temp);
          printf("Movemos Disco de la Estaca %d a la Estaca %d\n",inic,fin);
       hanoi(n-1,temp,inic,fin);
    }
 }

Iterativo

#include "iostream.h"
#include "conio.h"

void ToresDeHanoiIterativo(int nroDiscos,char origen,char destino,char auxiliar)
{
 char pilaO[10],pilaD[10],pilaX[10];
 int pilaN[10];
 int tope;
 char varaux;
 bool band;
 tope=0;
 band=false;
 while(nroDiscos>0 && band==false)
 {
   while(nroDiscos>1)
   {
     tope=tope+1;
     pilaN[tope]=nroDiscos;
     pilaO[tope]=origen;
     pilaD[tope]=destino;
     pilaX[tope]=auxiliar;
     nroDiscos=nroDiscos-1;
     varaux=destino;
     destino=auxiliar;
     auxiliar=varaux;
   }
   cout<<"Mover un disco de"<<origen<<"-->"<<destino<<endl;
   band=true;
   if(tope>0)
   {
   nroDiscos=pilaN[tope];
   origen=pilaO[tope];
   destino=pilaD[tope];
   auxiliar=pilaX[tope];
   tope=tope-1;
          cout<<"Mover un disco de"<<origen<<"-->"<<destino<<endl;
   nroDiscos=nroDiscos-1;
   varaux=origen;
   origen=auxiliar;
   auxiliar=varaux;
   band=false;
   }
 }
}
void main()
{
  int nroDiscos;
  cout<<"Ingrese el numero de discos:";
  cin>>nroDiscos;
  ToresDeHanoiIterativo(nroDiscos,'O','D','A');  
}

Los creditos del Iterativo para Mundo de la programación

¿Y para ti, cual es tu favorita?

  • Rubén

    Gracias, me sirvió para entender otro ejemplo, pero de DNS.

  • Eddy

    Deberías de probar con recursión de cola para poder igualar la eficiencia con la iteración

    • luisaca

      Solo era un ejemplo.

  • Pingback: Recursividad vs. Iteratividad - Código Máquina()

    • luisaca

      😉

  • The_menda14

    hannoi puede resolverse de una forma mas sencilla asi:

    void hanoi (int nDisco, char origen, char destino, char temporal){

    if (nDisco > 0){
    hannoi (nDisco -1, origen, temporal, destino);
    printf (“Muevo %d de %c a %cn”, nDisco, origen, destino);

    }

    }