Hasta donde yo sé, la mayoría de las funciones recursivas se pueden reescribir utilizando bucles. Algunos quizás sean más difíciles que otros, pero la mayoría se pueden reescribir.¿Qué funciones recursivas no pueden reescribirse utilizando bucles?
¿Bajo qué condiciones resulta imposible reescribir una función recursiva mediante un bucle (si existen tales condiciones)?
Cuando se utiliza una función recursiva, el compilador se encarga de la gestión de la pila para usted, que es lo que hace posible la recursividad. Todo lo que puede hacer recursivamente, lo puede hacer administrando una pila usted mismo (para la recursión indirecta, solo tiene que asegurarse de que sus diferentes funciones compartan esa pila).
Entonces, no, no hay nada que se pueda hacer con la recursión y eso no se puede hacer con un bucle y una pila.
Tengo una pregunta relacionada: ¿todas las funciones recursivas se pueden representar como ** un solo bucle **? –
@Abhinav: siento responder a un hilo muy antiguo, pero me llamó la atención y hay una prueba simple de que la respuesta es sí: una máquina de Turing hace todo lo que hace ejecutando un solo bucle: 1. obtener una instrucción, 2. evaluarlo, 3. goto 1. – mokus
@mokus Su prueba parece incompleta. El objetivo es demostrar que cada función recursiva se puede representar como un solo bucle.Estás diciendo que una TM se ejecuta en un solo bucle. ¿Dónde entra la recurrencia en esto? –
Todos ellos se pueden escribir como un bucle iterativo (pero algunos aún pueden necesitar una pila para mantener el estado anterior para iteraciones posteriores).
Siempre puede usar un bucle, pero es posible que deba crear más estructura de datos (por ejemplo, simular una pila).
No se trata de que no se puedan implementar utilizando bucles, sino que la forma en que funciona el algoritmo recursivo es mucho más clara y concisa (y en muchos casos matemáticamente demostrable) que una función es correcto.
Se pueden escribir muchas funciones recursivas para que sean recursivas de bucle de cola recursivas, que se pueden optimizar para un bucle, pero esto depende tanto del algoritmo como del idioma utilizado.
No sé acerca de ejemplos en los que las funciones recursivas no se puede convertir en una versión iterativa, pero los ejemplos poco prácticas o extremadamente ineficientes son:
recorrido del árbol
rápida de Fourier
quicksorts (y algunos otros iirc)
Básicamente, cualquier cosa en la que tengas que empezar a realizar un seguimiento de estados potenciales ilimitados.
Cualquier función recursiva se puede hacer para iterar (en un bucle) pero necesita usar una pila para mantener el estado.
Normalmente, la recursión de cola es fácil de convertir en un bucle:
A(x) {
if x<0 return 0;
return something(x) + A(x-1)
}
se puede traducir en:
A(x) {
temp = 0;
for i in 0..x {
temp = temp + something(i);
}
return temp;
}
Otros tipos de recursividad que se pueden traducir en la recursión de cola también son fáciles de cambio. El otro requiere más trabajo.
la siguiente:
treeSum(tree) {
if tree=nil then 0
else tree.value + treeSum(tree.left) + treeSum(tree.right);
}
no es tan fácil de traducir. Puede eliminar una parte de la recursión, pero la otra no es posible sin una estructura para mantener el estado.
treeSum(tree) {
walk = tree;
temp = 0;
while walk != nil {
temp = temp + walk.value + treeSum(walk.right);
walk = walk.left;
}
}
Su ejemplo recursivo de cola original no es completamente recursivo de cola (pero aún ilustra el punto esa recursividad "lineal" es a menudo fácil de traducir, mientras que las arias más altas a menudo no son tan fáciles). – Brian
Gracias. El último ejemplo parece ser lo que estoy buscando. ¿Es realmente imposible eliminar la recursión de ella? –
No, siempre puede reescribirlo con bucles. Es casi mecánico transformarlo en código que usa continuaciones, que pueden compilarse en bucles (no usar la pila) en un lenguaje como F #, ver p. http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!256.entry – Brian
Un ejemplo que sería extremadamente difícil convertir de recursiva para iterativos sería el Ackermann function.
Buen ejemplo. Pero queda una pregunta: ¿es imposible o simplemente extremadamente difícil? –
No es demasiado difícil si conoces las técnicas generales. – Brian
Traté de hacer esto, y no me parece difícil. Verifique este código (y por favor dígame si hay algún problema): ... –
La recursión indirecta todavía es posible convertir en un bucle no recursivo; solo comience con una de las funciones y alinee las llamadas a las demás hasta que tenga una función recursiva directa, que luego se puede traducir a un bucle que use una estructura de pila.
Cada función recursiva se puede implementar con un solo bucle.
Solo piense en lo que hace un procesador, ejecuta las instrucciones en un solo ciclo.
En realidad, no funciona como un bucle. La tubería en una CPU moderna se parece mucho más a una línea de ensamblaje. Comience en la instrucción uno, vaya a la siguiente instrucción en el puntero de instrucción ++. Algunas instrucciones modifican el puntero de la instrucción, lo que da como resultado un bucle o un salto. – Spence
@Spence El puntero de instrucción es solo información. – starblue
Es un poco más que solo datos. La mayor parte de la memoria caché de predicción de ramificación se ejecuta fuera de la posición y las instrucciones futuras previas se basan en el puntero. Aunque se puede modificar mediante el ensamblaje, es una parte fundamental del procesador. – Spence
En SICP, los autores desafían al lector a encontrar un método puramente iterativo para implementar el problema de "conteo de cambios" (here's an example del Proyecto Euler).
Pero la respuesta estricta a su pregunta ya fue dada: los bucles y las pilas pueden implementar cualquier recursión.
Sospecho que realmente quiere decir que no puede ser reescrito sin algún tipo de pila, ¿verdad? – AnthonyWJones
Realmente no. Quiero decir si es totalmente imposible reescribirlo usando un bucle. Estoy pensando en la recursión indirecta como un ejemplo. –
https://secweb.cs.odu.edu/~zeil/cs361/website/Website/Lectures/recursionConversion/page/recursionConversion.html – user1709408