Autor Tema: Recursión vs. iteración

0 Usuarios y 1 Visitante están viendo este tema.

30 Diciembre, 2014, 12:05 am
Leído 5617 veces

nanelito

  • $$\Large \color{red}\pi\,\pi\,\pi$$
  • Mensajes: 126
  • Karma: +0/-0
  • Sexo: Masculino
¿Existe un método para pasar de un algoritmo recursivo a uno iterativo y viceversa?

30 Diciembre, 2014, 01:24 am
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,282
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
No recuerdo bien los detalles, pero básicamente la cuestión es usar en la versión iterativa tantas variables como sean necesarias para reemplazar lo necesario en el proceso de recursión.

Al llamar a una subrutina, se crea una pila de datos, con las variables locales de la subrutina, y una copia de sus argumentos.
Al hacer la llamada en forma recursiva, en cada paso se crea una nueva pila de datos asociado a esa llamada recursiva.

El paso de "iterativo" a "recursivo" consistiría, entonces, en ir generando ese espacio para las pilas necesarias en cada llamada a la subrutina recursiva.

Si la recursión es simple, como la de la función factorial, que depende sólo de un avlor presente (el factorial de n necesita conocer sólo el factorial de n-1, olvidándose de cuáles eran los factoriales de valores precedentes), entonces la pila puede reducirse y quedar constante.

Si la llamada recursiva es compleja, el espacio asociado a la pila de llamadas recursivas no veo, así a ojo y sin recordar demasiado la teoría de este tema, cómo evitar que su tamaño crezca en cada iteración.

Pero bueno, que el tamaño de los datos crezca en cada paso no quita el hecho de que efectivamente se puede convertir recursión en iteración.

En cuanto al camino inverso, es más trivial, aunque si hay varias iteraciones anidadas con una lógica compleja de saltos en el interín, será complicado en la práctica encontrar la formulación recursiva correcta.

Lamento no poder responder mejor, espero haber ayudado en algo.

Saludos.

30 Diciembre, 2014, 02:28 am
Respuesta #2

nanelito

  • $$\Large \color{red}\pi\,\pi\,\pi$$
  • Mensajes: 126
  • Karma: +0/-0
  • Sexo: Masculino
Me regalas por ejemplo la versión recursiva de la función primo(n) que devuelve true si n es primo, caso contrario devuelve false
Primo(n)
Si \( n \leq 1 \)
    Retorne false;
Sino
    Si \( n=2 \;or\; n=3 \)
         Retorne true;
    Sino
         Si \( n \ mod 2= 0 \)
              Retorne false;
         Sino \( i\leftarrow 3,\; r\leftarrow \sqrt{n} \);
               Mientras \( i\leq r \;\&\& \;n\mod i\neq 0 \)
                                 \( i\leftarrow i+1 \);
                Si \( i>r \)
                      Retorne true;
                Sino Retorne false;
Fin primo(n)
... Me gustaría ver la version iterativa de la natural función buscar(n) en un árbol binario de búsqueda que almacena enteros!

30 Diciembre, 2014, 04:40 am
Respuesta #3

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,282
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Buscar en forma iterativa en un árbol de búsqueda, que ya está correctamente confeccionado, no debería representar ningún problema:

n = valor_buscado
p = nodo_raiz
mientras p != NULL && p->val != n
   Si (n <= p->val)
      p = p->izquierda
   Sino
      p = p->derecha
finmientras

Si p == NULL
   print "Valor n no encontrado en el árbol"
Sino
   print "Valor n existe en el árbol"

Salvo detalles de implementación, eso debiera funcionar, y es iterativo.

En cuanto a realizar una función recursiva de verificación de primos, me parece que puede resultar muy ineficiente.
Si estás pensando en guardar la lista de los primos anteriores en un árbol, lo óptimo sería, igual que en la versión iterativa, generar un árbol de los primos menores que sqrt(n), para ahorrar tiempo y espacio.

Supongamos que el número a verificar n es mayor que 4, y que descartamos los casos divisibles por 2 y por 3 (cosa que puede hacerse rápidamente antes de cualquier otra cosa más seria).

Entonces primo(n) tiene que tomar el número n y dividirlo por los primos menores que sqrt(n).
Suponiendo que queremos generarlos cada vez que llamamos la función primo(n),
esta listo de primos < sqrt(n) nunca está generada.
Habría que tomar la lista de números no divisibles por 2 ni por 3 (porque sigo con la misma filosofía que antes) menores que sqrt(n), y verfiicar si es primo o no.
Esto así planteado implica una iteración desde k igual 5 hasta sqrt(n), y llamar a primo(k) cada vez.

Así que la versión recursiva incluye una iteración en su interior.
Claro que esto es lo primero que se me ocurrió, y de cualquier manera que sea haga, será muy ineficiente.

Lograr simplificar este algoritmo es algo que seguramente se puede hacer sin mucha dificultad, pero requiere un esfuerzo que, al menos esta noche, no voy a hacer.

La clave está en que el árbol de primos menores que sqrt(n) se puede ir rellenando en cada paso recursivo, y no necesita volverse a crear en cada llamada.
Pensando en esto, y buscando estrategias adecuadas, se puede lograr un buen algoritmo recursivo.

En todo caso, una cosa es obtener un algoritmo recursivo o iterativo, y otra cosa es obtener un algoritmo eficiente, o un algoritmo claro.

Para los números primos nunca es fácil tener el mejor algoritmo, y muchas veces se termina guardando una lista con los primos menores que un cierto valor.

Existen algoritmos mucho más eficientes que no hacen nada de esto, pero hay que buscarlos por Internet. Yo no los he estudiado como para poder explicarlos.