recursivos recursivo recursividad recursivas propiedades multiple los iterativo iterativas funciones ejemplos complejidad algoritmos algorithm recursion iteration heuristics

algorithm - recursividad - Patrones de diseño para convertir algoritmos recursivos a iterativos



recursividad final y no final (7)

A menudo puede preservar por completo la estructura original de un algoritmo recursivo, pero evite la pila, empleando llamadas de cola y cambiando a continuación de paso , como lo sugiere esta entrada de blog . (Realmente debería cocinar un mejor ejemplo independiente.)

¿Hay alguna heurística general, consejos, trucos o paradigmas de diseño comunes que puedan emplearse para convertir un algoritmo recursivo en uno iterativo? Sé que se puede hacer, me pregunto si hay prácticas que vale la pena tener en cuenta al hacerlo.

A menudo, la recursividad general puede ser reemplazada por la recursividad de la cola, al recolectar resultados parciales en un acumulador y transmitirlo con la llamada recursiva. La recurrencia de la cola es esencialmente iterativa, la llamada recursiva se puede implementar como un salto.

Por ejemplo, la definición recursiva general estándar de factorial

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

puede ser reemplazado por

factorial(n) = f_iter(n, 1)

y

f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

que es cola recursiva Es lo mismo que

a = 1; while (n != 0) { a = n * a; n = n - 1; } return a;

Echa un vistazo a estos enlaces para ejemplos de rendimiento

Repetición VS Iteración (Looping): comparación de velocidad y memoria

y

Reemplazar recursión con iteración

y

Recursión vs iteración

P: ¿La versión recursiva suele ser más rápida? R: No, generalmente es más lento (debido a la sobrecarga de mantener la pila)

Q: Does the recursive version usually use less memory? A: No -- it usually uses more memory (for the stack). Q: Then why use recursion?? A: Sometimes it is much simpler to write the recursive version (but

tendremos que esperar hasta que hayamos discutido sobre los árboles para ver ejemplos realmente buenos ...)

Generalmente comienzo desde el caso base (cada función recursiva tiene uno) y trabajo hacia atrás, almacenando los resultados en un caché (matriz o hashtable) si es necesario.

Su función recursiva resuelve un problema resolviendo subproblemas más pequeños y usándolos para resolver la mayor instancia del problema. Cada subproblema también se desglosa más y más hasta que el subproblema es tan pequeño que la solución es trivial (es decir, el caso base).

La idea es comenzar en el caso base (o casos base) y usarlo para construir la solución para casos más grandes, y luego usarlos para construir casos aún más grandes, y así sucesivamente, hasta que se resuelva todo el problema. Esto no requiere una pila, y se puede hacer con bucles.

Un ejemplo simple (en Python):

#recursive version def fib(n): if n==0 or n==1: return n else: return fib(n-1)+fib(n-2) #iterative version def fib2(n): if n==0 or n==1: return n prev1,prev2=0,1 # start from the base case for i in xrange(n): cur=prev1+prev2 #build the solution for the next case using the previous solutions prev1,prev2=cur,prev1 return cur

Un patrón es la Recursividad de Cola :

Se dice que una llamada de función es recursiva de cola si no hay nada que hacer después de que la función retorna excepto que devuelve su valor.

Wiki .

Una práctica común es administrar una pila LIFO que mantiene una lista actualizada de lo que "queda por hacer" , y manejar todo el proceso en un ciclo while que continúa hasta que la lista esté vacía.
Con este patrón, lo que sería una llamada de recursión en el verdadero modelo de recursión es reemplazado por
- un empuje del "contexto" de la tarea actual (parcialmente terminada) en la pila,
- un empuje de la nueva tarea (la que provocó la recursión) en la pila
- y para "continuar" (es decir, saltar al comienzo de) el ciclo while. Cerca del principio del ciclo, la lógica muestra el contexto insertado más recientemente y comienza a trabajar sobre esta base.

Efectivamente, esto simplemente "mueve" la información que, de otro modo, se habría mantenido en los fotogramas apilados anidados en la pila del "sistema", a un contenedor de pila administrado por la aplicación. Sin embargo, es una mejora, ya que este contenedor de pila puede asignarse en cualquier lugar (el límite de recursión generalmente está vinculado a los límites en la pila del "sistema"). Por lo tanto, esencialmente se realiza el mismo trabajo, pero la administración explícita de una "pila" permite que esto tenga lugar dentro de una única construcción de bucle en lugar de llamadas recursivas.