Forma de pasar de la recursión a la iteración

He usado bastante la recursión en mis muchos años de progtwigción para resolver problemas simples, pero estoy totalmente consciente de que a veces se necesita iteración debido a problemas de memoria / velocidad.

Entonces, en el pasado, fui a intentar encontrar si existía una forma de “patrón” o libro de texto de transformar un enfoque de recursión común a la iteración y no encontré nada. O al menos nada que pueda recordar que ayude.

  • ¿Hay reglas generales?
  • ¿Hay un “patrón”?

    Usualmente, reemplazo un algoritmo recursivo por un algoritmo iterativo al presionar los parámetros que normalmente pasarían a la función recursiva en una stack. De hecho, estás reemplazando la stack de progtwigs por uno de los tuyos.

    Stack stack; stack.push(first_object); while( !stack.isEmpty() ) { // Do something my_object = stack.pop(); // Push other objects on the stack. } 

    Nota: si tiene más de una llamada recursiva en el interior y desea conservar el orden de las llamadas, debe agregarlas en orden inverso a la stack:

     foo(first); foo(second); 

    tiene que ser reemplazado por

     stack.push(second); stack.push(first); 

    Editar: El artículo Pila y Eliminación de recursión (o enlace de Copia de seguridad de artículo ) entra en más detalles sobre este tema.

    Realmente, la forma más común de hacerlo es mantener tu propia stack. Aquí hay una función de quicksort 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 podemos hacerlo iterativo manteniendo nuestra propia stack:

     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 stack … y realmente se puede dimensionar la stack en función del peor caso dado a los valores izquierdo y derecho. Pero se entiende la idea.

    Parece que nadie ha abordado donde la función recursiva se llama a sí misma más de una vez en el cuerpo, y maneja regresar a un punto específico en la recursión (es decir, no primitivo-recursivo). Se dice que cada recursión se puede convertir en iteración , por lo que parece que esto debería ser posible.

    Solo se me ocurrió un ejemplo de C # de cómo hacer esto. Supongamos que tiene la siguiente función recursiva, que actúa como un recorrido de postorder, y que AbcTreeNode es un árbol de 3 arios con punteros a, b, c.

     public static void AbcRecursiveTraversal(this AbcTreeNode x, List list) { if (x != null) { AbcRecursiveTraversal(xa, list); AbcRecursiveTraversal(xb, list); AbcRecursiveTraversal(xc, 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 = xa; address = A; break; case B: stack.Push(x); stack.Push(C); x = xb; address = A; break; case C: stack.Push(x); stack.Push(null); x = xc; address = A; break; case null: list_iterative.Add(x.key); @return = true; break; } } if (@return == true) { address = (int?)stack.Pop(); x = (AbcTreeNode)stack.Pop(); } } 

    Esfuércese por hacer su llamada recursiva Recursividad de cola (recursión donde la última statement es la llamada recursiva). Una vez que tienes eso, convertirlo a iteración es generalmente bastante fácil.

    Bueno, en general, la recursión puede ser imitada como iteración simplemente usando una variable de almacenamiento. Tenga en cuenta que la recursividad y la iteración son generalmente equivalentes; uno casi siempre puede convertirse al otro. Una función recursiva de cola se convierte fácilmente en una iterativa. Simplemente haga que la variable del acumulador sea local e itere en lugar de recurrir. Aquí hay un ejemplo en C ++ (C si no fuera por el uso de un argumento predeterminado):

     // tail-recursive int factorial (int n, int acc = 1) { if (n == 1) return acc; else return factorial(n - 1, acc * n); } // iterative int factorial (int n) { int acc = 1; for (; n > 1; --n) acc *= n; return acc; } 

    Conociéndome, probablemente cometí un error en el código, pero la idea está ahí.

    Incluso el uso de la stack no convertirá un algoritmo recursivo en iterativo. La recursión normal es la recursión basada en funciones y si usamos la stack, entonces se convierte en una recursión basada en la stack. Pero sigue siendo recurrencia.

    Para los algoritmos recursivos, la complejidad del espacio es O (N) y la complejidad del tiempo es O (N). Para los algoritmos iterativos, la complejidad del espacio es O (1) y la complejidad del tiempo es O (N).

    Pero si utilizamos las cosas de la stack en términos de complejidad, permanece igual. Creo que solo la recursividad de la cola se puede convertir en iteración.

    El artículo de eliminación de stacks y recursión captura la idea de externalizar el marco de stack en el montón, pero no proporciona una forma sencilla y repetible de convertir. Debajo hay uno.

    Al convertir a código iterativo, uno debe saber que la llamada recursiva puede ocurrir desde un bloque de código arbitrariamente profundo. No solo son los parámetros, sino también el punto para volver a la lógica que queda por ejecutar y el estado de las variables que participan en los condicionales subsiguientes, que son importantes. A continuación se muestra una forma muy simple de convertir a código iterativo con los mínimos cambios.

    Considera este código recursivo:

     struct tnode { tnode(int n) : data(n), left(0), right(0) {} tnode *left, *right; int data; }; void insertnode_recur(tnode *node, int num) { if(node->data < = num) { if(node->right == NULL) node->right = new tnode(num); else insertnode(node->right, num); } else { if(node->left == NULL) node->left = new tnode(num); else insertnode(node->left, num); } } 

    Código iterativo:

     // Identify the stack variables that need to be preserved across stack // invocations, that is, across iterations and wrap them in an object struct stackitem { stackitem(tnode *t, int n) : node(t), num(n), ra(0) {} tnode *node; int num; int ra; //to point of return }; void insertnode_iter(tnode *node, int num) { vector v; //pushing a stackitem is equivalent to making a recursive call. v.push_back(stackitem(node, num)); while(v.size()) { // taking a modifiable reference to the stack item makes prepending // 'si.' to auto variables in recursive logic suffice // eg, instead of num, replace with si.num. stackitem &si = v.back(); switch(si.ra) { // this jump simulates resuming execution after return from recursive // call case 1: goto ra1; case 2: goto ra2; default: break; } if(si.node->data < = si.num) { if(si.node->right == NULL) si.node->right = new tnode(si.num); else { // replace a recursive call with below statements // (a) save return point, // (b) push stack item with new stackitem, // (c) continue statement to make loop pick up and start // processing new stack item, // (d) a return point label // (e) optional semi-colon, if resume point is an end // of a block. si.ra=1; v.push_back(stackitem(si.node->right, si.num)); continue; ra1: ; } } else { if(si.node->left == NULL) si.node->left = new tnode(si.num); else { si.ra=2; v.push_back(stackitem(si.node->left, si.num)); continue; ra2: ; } } v.pop_back(); } } 

    Observe cómo la estructura del código sigue siendo fiel a la lógica recursiva y las modificaciones son mínimas, lo que resulta en una menor cantidad de errores. Para la comparación, he marcado los cambios con ++ y -. La mayoría de los nuevos bloques insertados excepto v.push_back, son comunes a cualquier lógica iterativa convertida

     void insertnode_iter(tnode *node, int num) { 

    +++++++++++++++++++++++++

      vector v; v.push_back(stackitem(node, num)); while(v.size()) { stackitem &si = v.back(); switch(si.ra) { case 1: goto ra1; case 2: goto ra2; default: break; } 

    ------------------------

      if(si.node->data < = si.num) { if(si.node->right == NULL) si.node->right = new tnode(si.num); else { 

    +++++++++++++++++++++++++

      si.ra=1; v.push_back(stackitem(si.node->right, si.num)); continue; ra1: ; 

    -------------------------

      } } else { if(si.node->left == NULL) si.node->left = new tnode(si.num); else { 

    +++++++++++++++++++++++++

      si.ra=2; v.push_back(stackitem(si.node->left, si.num)); continue; ra2: ; 

    -------------------------

      } } 

    +++++++++++++++++++++++++

      v.pop_back(); } 

    -------------------------

     } 

    Busque en google “Estilo de continuación de paso”. Hay un procedimiento general para convertir a un estilo recursivo de cola; también hay un procedimiento general para convertir las funciones recursivas de la cola en bucles.

    Simplemente matando el tiempo … Una función recursiva

     void foo(Node* node) { if(node == NULL) return; // Do something with node... foo(node->left); foo(node->right); } 

    se puede convertir a

     void foo(Node* node) { if(node == NULL) return; // Do something with node... stack.push(node->right); stack.push(node->left); while(!stack.empty()) { node1 = stack.pop(); if(node1 == NULL) continue; // Do something with node1... stack.push(node1->right); stack.push(node1->left); } } 

    En general, la técnica para evitar el desbordamiento de la stack es para las funciones recursivas se llama técnica de trampolín, que es ampliamente adoptada por los desarrolladores de Java.

    Sin embargo, para C # hay aquí un pequeño método auxiliar que convierte su función recursiva en iterativa sin necesidad de cambiar la lógica o hacer que el código sea comprensible. C # es un lenguaje tan agradable que cosas increíbles son posibles con él.

    Funciona envolviendo partes del método mediante un método de ayuda. Por ejemplo, la siguiente función recursiva:

     int Sum(int index, int[] array) { //This is the termination condition if (int >= array.Length) //This is the returning value when termination condition is true return 0; //This is the recursive call var sumofrest = Sum(index+1, array); //This is the work to do with the current item and the //result of recursive call return array[index]+sumofrest; } 

    Se convierte en:

     int Sum(int[] ar) { return RecursionHelper.CreateSingular(i => i >= ar.Length, i => 0) .RecursiveCall((i, rv) => i + 1) .Do((i, rv) => ar[i] + rv) .Execute(0); } 

    Un patrón que hay que buscar es una llamada de recursión al final de la función (llamada recursión final). Esto puede ser reemplazado fácilmente por un tiempo. Por ejemplo, la función foo:

     void foo(Node* node) { if(node == NULL) return; // Do something with node... foo(node->left); foo(node->right); } 

    termina con un llamado a foo. Esto puede ser reemplazado por:

     void foo(Node* node) { while(node != NULL) { // Do something with node... foo(node->left); node = node->right; } } 

    que elimina la segunda llamada recursiva.

    Acabo de subir la respuesta que sugiere utilizar una stack explícita que creo que es la solución correcta y de aplicación general.

    Quiero decir que puedes usarlo para transformar cualquier función recursiva en una función iterativa. Simplemente compruebe qué valores se guardan en las llamadas recursivas, esos son los que tienen que ser locales para la función recursiva, y reemplace las llamadas con un ciclo donde los empujará en una stack. Cuando la stack está vacía, la función recursiva habría terminado.

    No puedo resistirme a decir que la prueba de que cada función recursiva es equivalente a una función iterativa en un tipo de datos diferente, es uno de mis recuerdos más queridos de mi tiempo en la Universidad. Ese fue el curso (y el profesor) que realmente me hizo entender de qué se trataba la progtwigción de computadoras.

    Una pregunta que se había cerrado como un duplicado de esta tenía una estructura de datos muy específica:

    enter image description here

    El nodo tenía la siguiente estructura:

     typedef struct { int32_t type; int32_t valueint; double valuedouble; struct cNODE *next; struct cNODE *prev; struct cNODE *child; } cNODE; 

    La función de eliminación recursiva se veía así:

     void cNODE_Delete(cNODE *c) { cNODE*next; while (c) { next=c->next; if (c->child) { cNODE_Delete(c->child) } free(c); c=next; } } 

    En general, no siempre es posible evitar una stack para funciones recursivas que se invocan más de una vez (o incluso una vez). Sin embargo, para esta estructura particular, es posible. La idea es aplanar todos los nodos en una sola lista. Esto se logra colocando el child del nodo actual al final de la lista de la fila superior.

     void cNODE_Delete (cNODE *c) { cNODE *tmp, *last = c; while (c) { while (last->next) { last = last->next; /* find last */ } if ((tmp = c->child)) { c->child = NULL; /* append child to last */ last->next = tmp; tmp->prev = last; } tmp = c->next; /* remove current */ free(c); c = tmp; } } 

    Esta técnica se puede aplicar a cualquier estructura vinculada a datos que se pueda reducir a un DAG con un ordenamiento topológico determinista. Los nodos actuales se reordenan para que el último hijo adopte a todos los otros hijos. Entonces, el nodo actual puede eliminarse y el recorrido puede iterar al niño restante.

    La recursividad no es más que el proceso de llamar a una función de la otra, solo que este proceso se realiza llamando a una función por sí mismo. Como sabemos cuando una función llama a la otra función, la primera función guarda su estado (sus variables) y luego pasa el control a la función llamada. La función llamada se puede llamar usando el mismo nombre de las variables ex fun1 (a) puede llamar a fun2 (a). Cuando hacemos una llamada recursiva, no sucede nada nuevo. Una función se llama pasando el mismo tipo y las variables de nombre similares (pero obviamente los valores almacenados en las variables son diferentes, solo el nombre permanece igual) en sí mismo. Pero antes de cada llamada la función guarda su estado y este proceso de ahorro continúa. El AHORRO SE HACE EN UNA PILA.

    AHORA LA PILA ESTÁ EN JUEGO.

    Entonces, si usted escribe un progtwig iterativo y guarda el estado en una stack cada vez y luego extrae los valores de la stack cuando es necesario, ¡ha convertido con éxito un progtwig recursivo en uno iterativo!

    La prueba es simple y analítica.

    En recursión, la computadora mantiene una stack y, en la versión iterativa, tendrá que mantener manualmente la stack.

    Piénselo, simplemente convierta un progtwig recursivo de búsqueda de profundidad (en gráficos) en un progtwig iterativo de dfs.

    ¡Todo lo mejor!

    Pensando en cosas que realmente necesitan una stack:

    Si consideramos el patrón de recursión como:

     if(task can be done directly) { return result of doing task directly } else { split task into two or more parts solve for each part (possibly by recursing) return result constructed by combining these solutions } 

    Por ejemplo, la clásica Torre de Hanoi

     if(the number of discs to move is 1) { just move it } else { move n-1 discs to the spare peg move the remaining disc to the target peg move n-1 discs from the spare peg to the target peg, using the current peg as a spare } 

    Esto se puede traducir en un bucle trabajando en una stack explícita, reformulándolo como:

     place seed task on stack while stack is not empty take a task off the stack if(task can be done directly) { Do it } else { Split task into two or more parts Place task to consolidate results on stack Place each task on stack } } 

    Para la Torre de Hanoi esto se convierte en:

     stack.push(new Task(size, from, to, spare)); while(! stack.isEmpty()) { task = stack.pop(); if(task.size() = 1) { just move it } else { stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from())); stack.push(new Task(1, task.from(), task.to(), task.spare())); stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to())); } } 

    Aquí hay una considerable flexibilidad en cuanto a cómo defines tu stack. Puede hacer que su stack sea una lista de objetos Command que hacen cosas sofisticadas. O puede ir en la dirección opuesta y hacer que sea una lista de tipos más simples (por ejemplo, una “tarea” podría ser 4 elementos en una stack de int , en lugar de un elemento en una stack de Task ).

    Todo esto significa que la memoria para la stack está en el montón en lugar de en la stack de ejecución de Java, pero esto puede ser útil porque usted tiene más control sobre ella.

    Una descripción aproximada de cómo un sistema toma cualquier función recursiva y la ejecuta usando una stack:

    Esto pretendía mostrar la idea sin detalles. Considere esta función que imprimiría nodos de un gráfico:

     function show(node) 0. if isleaf(node): 1. print node.name 2. else: 3. show(node.left) 4. show(node) 5. show(node.right) 

    Por ejemplo, gráfico: A-> B A-> C show (A) imprimiría B, A, C

    Las llamadas a funciones significan guardar el estado local y el punto de continuación para que pueda volver, y luego saltar la función a la que desea llamar.

    Por ejemplo, supongamos que show (A) comienza a ejecutarse. La función invocar en la línea 3. mostrar (B) significa – Agregar elemento a la stack significando que “tendrá que continuar en la línea 2 con estado variable local nodo = A” – Ir a la línea 0 con nodo = B.

    Para ejecutar el código, el sistema ejecuta las instrucciones. Cuando se encuentra una llamada de función, el sistema transfiere la información que necesita para volver a donde estaba, ejecuta el código de la función y, cuando la función se completa, muestra la información sobre dónde debe continuar para continuar.

    Este enlace proporciona algunas explicaciones y propone la idea de mantener “ubicación” para poder llegar al lugar exacto entre varias llamadas recursivas:

    Sin embargo, todos estos ejemplos describen escenarios en los que una llamada recursiva se realiza una cantidad fija de veces. Las cosas se vuelven más complicadas cuando tienes algo como:

     function rec(...) { for/while loop { var x = rec(...) // make a side effect involving return value x } } 

    Existe una forma general de convertir el recorrido recursivo a iterador mediante el uso de un iterador diferido que concatena múltiples proveedores de iterador (expresión lambda que devuelve un iterador). Ver mi conversión Recursive Recursive to Iterator .

    Otro ejemplo simple y completo de convertir la función recursiva en iterativa utilizando la stack.

     #include  #include  using namespace std; int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); } struct Par { int a, b; Par() : Par(0, 0) {} Par(int _a, int _b) : a(_a), b(_b) {} }; int GCDIter(int a, int b) { stack rcstack; if (b == 0) return a; rcstack.push(Par(b, a % b)); Par p; while (!rcstack.empty()) { p = rcstack.top(); rcstack.pop(); if (pb == 0) continue; rcstack.push(Par(pb, pa % pb)); } return pa; } int main() { //cout < < GCD(24, 36) << endl; cout << GCDIter(81, 36) << endl; cin.get(); return 0; }