recursion - recursiva - recursividad ejemplos
Camino a ir de la recursión a la iteración. (19)
He usado bastante la recursión en mis muchos años de programación para resolver problemas simples, pero soy consciente de que a veces necesitas iteración debido a problemas de memoria / velocidad.
Así que, en el pasado, fui a tratar de encontrar si existía algún "patrón" o forma de libro de texto para transformar un enfoque de recursión común a la iteración y no encontrar nada. O al menos nada de lo que pueda recordar me ayudaría.
- ¿Hay reglas generales?
- ¿Hay un "patrón"?
Acabo de anunciar la respuesta que sugiere el uso de una pila explícita que creo que es la solución correcta y es de aplicación general.
Quiero decir que puedes usarlo para transformar cualquier función recursiva en una función iterativa. Solo verifique qué valores se guardan en las llamadas recursivas, esos son los que tienen que ser locales a la función recursiva, y reemplace las llamadas con un ciclo en el que los empujará en una pila. Cuando la pila está vacía, la función recursiva se 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 preciados de mis tiempos universitarios. Ese fue el curso (y el profesor) que realmente me hizo entender de qué se trataba la programación de computadoras.
Bueno, en general, la recursión puede imitarse como iteración simplemente usando una variable de almacenamiento. Tenga en cuenta que la recursividad y la interacción son generalmente equivalentes; Uno casi siempre se puede convertir al otro. Una función recursiva de la cola se convierte muy fácilmente a una iterativa. Solo haga que la variable del acumulador sea una local, y repita en lugar de repetir. 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í.
Busque en google "Estilo de paso de la continuación". Existe 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.
El artículo de eliminación de pilas y recursión captura la idea de externalizar el marco de pila en el montón, pero no proporciona una forma directa y repetible de convertir. Abajo hay uno.
Al convertir a código iterativo, uno debe ser consciente de que la llamada recursiva puede ocurrir desde un bloque de código arbitrariamente profundo. No son solo 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 posteriores, lo que importa. A continuación se muestra una forma muy sencilla de convertir a código iterativo con menos 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<stackitem> 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
// e.g., 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 da como resultado un menor número de errores. Para comparar, 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<stackitem> 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();
}
-------------------------
}
En general, la técnica para evitar el desbordamiento de pila para funciones recursivas se denomina técnica de trampolín y es ampliamente adoptada por los desarrolladores de Java.
Sin embargo, para C # hay un pequeño método auxiliar here que convierte su función recursiva en iterativa sin necesidad de cambiar la lógica o hacer que el código sea incomprensible. C # es un lenguaje tan bonito que con él se pueden hacer cosas increíbles.
Funciona envolviendo partes del método con un método auxiliar. 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<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
Este link proporciona una explicación 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 complican 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 en iterador utilizando un iterador perezoso que concatena múltiples proveedores de iteradores (expresión lambda que devuelve un iterador). Ver mi Conversión recursiva transversal a iterador .
Incluso el uso de la pila no convertirá un algoritmo recursivo en iterativo. La recursión normal es una recursión basada en la función y si usamos pila, entonces se convierte en recursión basada en la pila. Pero todavía es una recursión.
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 usamos cosas de pila en términos de complejidad sigue siendo el mismo. Creo que solo la recursión de la cola se puede convertir en iteración.
La recursión no es más que el proceso de llamar a una función desde la otra, solo este proceso se realiza llamando a una función por sí misma. Como sabemos que cuando una función llama a la otra función, la primera guarda su estado (sus variables) y luego pasa el control a la función llamada. Se puede llamar a la función llamada usando el mismo nombre de las variables que ex fun1 (a) puede llamar fun2 (a). Cuando hacemos llamadas recursivas no pasa nada nuevo. Una función se llama a sí misma pasando el mismo tipo y similar en las variables de nombre (pero obviamente los valores almacenados en las variables son diferentes, solo el nombre permanece igual) a sí mismo. Pero antes de cada llamada, la función guarda su estado y este proceso de guardado continúa. El ahorro se hace en una pila.
Ahora la pila entra en juego.
Entonces, si escribe un programa iterativo y guarda el estado en una pila cada vez y luego saca los valores de la pila cuando sea necesario, ¡ha convertido un programa recursivo en uno iterativo!
La prueba es simple y analítica.
En la recursión, la computadora mantiene una pila y en la versión iterativa tendrá que mantener manualmente la pila.
Piénselo, simplemente convierta un programa recursivo de búsqueda en profundidad (en gráficos) en un programa iterativo dfs.
¡Todo lo mejor!
Otro ejemplo simple y completo de convertir la función recursiva en iterativa usando la pila.
#include <iostream>
#include <stack>
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<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
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 regresar a un punto específico en la recursión (es decir, no primitivo-recursivo). Se dice que cada recursión puede convertirse en iteración , por lo que parece que esto debería ser posible.
Acabo de llegar con un ejemplo de C # de cómo hacer esto. Supongamos que tiene la siguiente función recursiva, que actúa como un recorrido transversal de orden posterior, y que AbcTreeNode es un árbol 3-ario 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();
}
}
Pensando en cosas que realmente necesitan una pila:
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 que funciona en una pila explícita, al reformularlo 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()));
}
}
Hay una considerable flexibilidad aquí en cuanto a cómo definir su pila. Puedes hacer de tu pila una lista de objetos de 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" puede ser 4 elementos en una pila de int , en lugar de un elemento en una pila de Task ).
Todo lo que esto significa es que la memoria para la pila está en el montón en lugar de en la pila de ejecución de Java, pero esto puede ser útil porque tiene más control sobre ella.
Por lo general, sustituyo un algoritmo recursivo por un algoritmo iterativo presionando los parámetros que normalmente se pasarían a la función recursiva en una pila. De hecho, está reemplazando la pila de programas por una propia.
Stack<Object> 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 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);
Edición: el artículo sobre las pilas y la eliminación de la recursión (o el enlace de copia de seguridad del artículo ) incluye más detalles sobre este tema.
Realmente, la forma más común de hacerlo es mantener tu propia pila. Aquí hay una función de orden 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 comprueba los límites de la pila ... y realmente podría ajustar el tamaño de la pila en función del peor caso dado a los valores izquierdo y derecho. Pero se entiende la idea.
Solo 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);
}
}
Trate de hacer su llamada recursiva Recursión de cola (recursión donde la última instrucción es la llamada recursiva). Una vez que tienes eso, convertirlo a iteración es generalmente bastante fácil.
Un patrón que debe buscarse es una llamada de recursión al final de la función (llamada cola recursiva). Esto puede ser fácilmente reemplazado con 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 una llamada a foo. Esto puede ser reemplazado con:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
Lo que elimina la segunda llamada recursiva.
Una descripción aproximada de cómo un sistema toma cualquier función recursiva y la ejecuta utilizando una pila:
Esto pretendía mostrar la idea sin detalles. Considere esta función que imprimiría los 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á B, A, C
Las llamadas a funciones significan guardar el estado local y el punto de continuación para que pueda regresar y luego saltar a la función que desea llamar.
Por ejemplo, supongamos que show (A) comienza a ejecutarse. La función de llamada en la línea 3. show (B) significa - Agregar elemento a la pila que significa "necesitará continuar en la línea 2 con el estado del estado variable local = A" - Ir a la línea 0 con el nodo = B.
Para ejecutar el código, el sistema ejecuta las instrucciones. Cuando se encuentra una llamada a una función, el sistema envía 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 ir para continuar.
Una question que se había cerrado como un duplicado de ésta tenía una estructura de datos muy específica:
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 parecía:
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 pila 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 al poner al 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 de enlace de datos que se pueda reducir a un DAG con un ordenamiento topológico determinista. Los nodos actuales de los niños se reorganizan para que el último niño adopte a todos los demás niños. Luego, el nodo actual se puede eliminar y el recorrido puede entonces iterar hasta el elemento secundario restante.