Manera de pasar de la recursividad a la iteración
He usado bastante la recursividad durante mis muchos años de programación para resolver problemas simples, pero soy plenamente consciente de que a veces es necesario iterar debido a problemas de memoria/velocidad.
Entonces, en algún momento en el pasado lejano intenté encontrar si existía algún "patrón" o forma de libro de texto para transformar un enfoque recursivo común para la iteración y no encontré nada. O al menos nada que pueda recordar ayudaría.
- ¿Existen reglas generales?
- ¿Existe un "patrón"?
Por lo general, reemplazo un algoritmo recursivo por un algoritmo iterativo al insertar en una pila los parámetros que normalmente se pasarían a la función recursiva. De hecho, estás reemplazando la pila de programas por una propia.
var stack = [];
stack.push(firstObject);
// while not empty
while (stack.length) {
// Pop off end of stack.
obj = stack.pop();
// Do stuff.
// Push other objects on the stack as needed.
...
}
Nota: si tiene más de una llamada recursiva dentro y desea conservar el orden de las llamadas, debe agregarlas en orden inverso a la pila:
foo(first);
foo(second);
tiene que ser reemplazado por
stack.push(second);
stack.push(first);
Editar: el artículo Eliminación de pilas y recursividad (o enlace de copia de seguridad del artículo ) proporciona más detalles sobre este tema.
Realmente, la forma más común de hacerlo es conservar tu propia pila. Aquí hay una función de ordenación rápida recursiva en C:
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
Así es como podríamos hacerlo iterativo manteniendo nuestra propia pila:
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
Obviamente, este ejemplo no verifica los límites de la pila... y realmente podría dimensionar la pila basándose en el peor de los casos, dados los valores izquierdo y derecho. Pero se entiende la idea.
Parece que nadie ha abordado dónde la función recursiva se llama a sí misma más de una vez en el cuerpo y maneja el regreso a un punto específico en la recursividad (es decir, no primitivo-recursivo). Se dice que cada recursividad se puede convertir en iteración , por lo que parece que esto debería ser posible.
Se me ocurrió un ejemplo en C# de cómo hacer esto. Suponga que tiene la siguiente función recursiva, que actúa como un recorrido de postorden, y que AbcTreeNode es un árbol triario con punteros a, b, c.
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
list.Add(x.key);//finally visit root
}
}
La solución iterativa:
int? address = null;
AbcTreeNode x = null;
x = root;
address = A;
stack.Push(x);
stack.Push(null)
while (stack.Count > 0) {
bool @return = x == null;
if (@return == false) {
switch (address) {
case A://
stack.Push(x);
stack.Push(B);
x = x.a;
address = A;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
address = A;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
address = A;
break;
case null:
list_iterative.Add(x.key);
@return = true;
break;
}
}
if (@return == true) {
address = (int?)stack.Pop();
x = (AbcTreeNode)stack.Pop();
}
}
