¿Puede cada recursión convertirse en iteración?

Un hilo reddit trajo una pregunta aparentemente interesante:

Las funciones recursivas de cola pueden convertirse trivialmente en funciones iterativas. Otros, se pueden transformar utilizando una stack explícita. ¿Puede cada recursión transformarse en iteración?

El (contador?) Ejemplo en la publicación es el par:

(define (num-ways xy) (case ((= x 0) 1) ((= y 0) 1) (num-ways2 xy) )) (define (num-ways2 xy) (+ (num-ways (- x 1) y) (num-ways x (- y 1)) 

¿Puedes convertir siempre una función recursiva en una iterativa? Sí, absolutamente, y la tesis Church-Turing lo prueba si la memoria sirve. En términos simples, establece que lo que es computable por funciones recursivas es computable por un modelo iterativo (como la máquina de Turing) y viceversa. La tesis no le dice exactamente cómo hacer la conversión, pero sí dice que definitivamente es posible.

En muchos casos, la conversión de una función recursiva es fácil. Knuth ofrece varias técnicas en “El arte de la progtwigción de computadoras”. Y a menudo, una cosa calculada recursivamente puede ser calculada por un enfoque completamente diferente en menos tiempo y espacio. El ejemplo clásico de esto son los números de Fibonacci o sus secuencias. Seguramente has encontrado este problema en tu plan de estudios.

En la otra cara de la moneda, podemos imaginar un sistema de progtwigción tan avanzado como para tratar una definición recursiva de una fórmula como una invitación a memorizar resultados previos, ofreciendo así el beneficio de velocidad sin la molestia de decirle a la computadora exactamente qué pasos seguir en el cálculo de una fórmula con una definición recursiva. Dijkstra casi con seguridad imaginó tal sistema. Pasó un largo tiempo tratando de separar la implementación de la semántica de un lenguaje de progtwigción. Por otra parte, sus lenguajes de progtwigción no deterministas y de multiprocesamiento están en una liga por encima del progtwigdor profesional en ejercicio.

En el análisis final, muchas funciones son simplemente más fáciles de entender, leer y escribir en forma recursiva. A menos que exista una razón convincente, probablemente no deba (manualmente) convertir estas funciones a un algoritmo explícitamente iterativo. Su computadora manejará ese trabajo correctamente.

Puedo ver una razón convincente. Supongamos que tiene un sistema prototipo en un lenguaje de súper alto nivel como [ ponerse ropa interior de amianto ] Scheme, Lisp, Haskell, OCaml, Perl o Pascal. Supongamos que las condiciones son tales que necesita una implementación en C o Java. (Tal vez sea política.) Entonces ciertamente podría tener algunas funciones escritas recursivamente pero que, traducidas literalmente, explotarían su sistema de tiempo de ejecución. Por ejemplo, la recursión infinita de cola es posible en Scheme, pero la misma expresión idiomática causa un problema para los entornos C existentes. Otro ejemplo es el uso de funciones anidadas léxicamente y el scope estático, que Pascal admite pero C no.

En estas circunstancias, puede tratar de superar la resistencia política al idioma original. Puede que te encuentres reimplantando mal a Lisp, como en la décima ley de Greenspun (irónico). O tal vez solo encuentre un enfoque completamente diferente a la solución. Pero en cualquier caso, seguramente hay una manera.

¿Siempre es posible escribir un formulario no recursivo para cada función recursiva?

Sí. Una prueba formal simple es mostrar que tanto la recursión μ como un cálculo no recursivo como GOTO están completos. Como todos los cálculos completos de Turing son estrictamente equivalentes en su poder expresivo, todas las funciones recursivas pueden implementarse mediante el cálculo no repetitivo de Turing completo.

Lamentablemente, no puedo encontrar una buena definición formal de GOTO en línea, así que aquí hay una:

Un progtwig GOTO es una secuencia de comandos P ejecutados en una máquina registradora de manera que P es uno de los siguientes:

  • HALT , que detiene la ejecución
  • r = r + 1 donde r es cualquier registro
  • r = r – 1 donde r es cualquier registro
  • GOTO x donde x es una etiqueta
  • IF r ≠ 0 GOTO x donde r es cualquier registro y x es una etiqueta
  • Una etiqueta, seguida de cualquiera de los comandos anteriores.

Sin embargo, las conversiones entre las funciones recursivas y no recursivas no siempre son triviales (excepto por la reimplantación manual sin sentido de la stack de llamadas).

La recursión se implementa como stacks o construcciones similares en los intérpretes o comstackdores reales. Entonces, ciertamente puede convertir una función recursiva a una contraparte iterativa porque así es como siempre se hace (si es automática) . Simplemente estará duplicando el trabajo del comstackdor de una manera ad-hoc y probablemente de una manera muy fea e ineficiente.

Básicamente sí, en esencia, lo que terminas teniendo que hacer es reemplazar las llamadas a métodos (que implícitamente presionan el estado en la stack) en astackmientos de stack explícitos para recordar dónde se había iniciado la ‘llamada anterior’ y luego ejecutar el ‘método llamado’ en lugar.

Me imagino que la combinación de un bucle, una stack y una máquina de estados se podría utilizar para todos los escenarios, básicamente simulando las llamadas al método. Si esto va a ser ‘mejor’ (o más rápido o más eficiente en cierto sentido) no es posible decirlo en general.

Sí, usando explícitamente una stack (pero la recursividad es mucho más agradable de leer, en mi humilde opinión).

  • El flujo de ejecución de la función recursiva se puede representar como un árbol.

  • La misma lógica puede ser hecha por un bucle, que usa una estructura de datos para atravesar ese árbol.

  • El recorrido en profundidad se puede hacer usando una stack, el recorrido de ancho se puede hacer usando una cola.

Entonces, la respuesta es: sí. Por qué: https://stackoverflow.com/a/531721/2128327 .

¿Se puede hacer una recursión en un solo ciclo? Sí porque

una máquina de Turing hace todo lo que hace ejecutando un solo bucle:

  1. buscar una instrucción,
  2. evaluarlo,
  3. Ir a 1.

Sí, siempre es posible escribir una versión no recursiva. La solución trivial es usar una estructura de datos de stack y simular la ejecución recursiva.

En principio, siempre es posible eliminar la recursión y reemplazarla con iteración en un idioma que tiene un estado infinito tanto para las estructuras de datos como para la stack de llamadas. Esta es una consecuencia básica de la tesis de Church-Turing.

Dado un lenguaje de progtwigción real, la respuesta no es tan obvia. El problema es que es bastante posible tener un lenguaje donde la cantidad de memoria que se puede asignar en el progtwig sea limitada, pero donde la cantidad de la stack de llamadas que se puede usar no esté limitada (C de 32 bits donde la dirección de las variables de la stack no es accesible). En este caso, la recursión es más poderosa simplemente porque tiene más memoria que puede usar; no hay suficiente memoria explícitamente asignable para emular la stack de llamadas. Para una discusión detallada sobre esto, vea esta discusión .

A veces, reemplazar la recursividad es mucho más fácil que eso. La recursividad solía ser lo más popular enseñado en CS en la década de 1990, por lo que muchos desarrolladores promedio de esa época pensaban que si resolvía algo con recursividad, era una solución mejor. Entonces utilizarían la recursión en lugar de hacer un ciclo hacia atrás para invertir el orden, o cosas así de tontas. Por lo tanto, a veces eliminar la recidiva es un simple tipo de ejercicio “duh, eso era obvio”.

Esto no es un problema ahora, ya que la moda se ha desplazado hacia otras tecnologías.

Todas las funciones computables pueden ser calculadas por Turing Machines y, por lo tanto, los sistemas recursivos y las máquinas de Turing (sistemas iterativos) son equivalentes.

Eliminar la recursividad es un problema complejo y es factible en circunstancias bien definidas.

Los siguientes casos se encuentran entre los más fáciles:

  • recursividad de la cola
  • recursión lineal directa

Además de la stack explícita, otro patrón para convertir la recursión en iteración es con el uso de un trampolín.

Aquí, las funciones devuelven el resultado final o un cierre de la llamada de función que de otro modo habría realizado. Luego, la función de iniciación (trampolín) sigue invocando los cierres devueltos hasta que se alcanza el resultado final.

Este enfoque funciona para funciones mutuamente recursivas, pero me temo que solo funciona para llamadas finales.

http://en.wikipedia.org/wiki/Trampoline_(computers)

Yo diría que sí, una llamada a función no es más que una operación de ir y una stack (hablando en términos generales). Todo lo que necesita hacer es imitar la stack que se genera al invocar funciones y hacer algo similar como un goto (puede imitar los gotos con lenguajes que no tienen explícitamente esta palabra clave también).

Eche un vistazo a las siguientes entradas en wikipedia, puede usarlas como punto de partida para encontrar una respuesta completa a su pregunta.

  • Recursividad en informática
  • Relación de recurrencia

Sigue un párrafo que puede darle alguna pista sobre dónde comenzar:

Resolver una relación de recurrencia significa obtener una solución de forma cerrada : una función no recursiva de n.

También eche un vistazo al último párrafo de esta entrada .

Es posible convertir cualquier algoritmo recursivo en uno no recursivo, pero a menudo la lógica es mucho más compleja y para hacerlo se requiere el uso de una stack. De hecho, la recursividad usa una stack: la stack de funciones.

Más detalles: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

tazzego, recursion significa que una función se llamará a sí misma, te guste o no. Cuando las personas hablan sobre si las cosas se pueden hacer sin recurrencia, significan esto y no se puede decir “no, eso no es cierto, porque no estoy de acuerdo con la definición de recursión” como una statement válida.

Con eso en mente, casi todo lo demás que dices es una tontería. La única otra cosa que dices que no es una tontería es la idea de que no puedes imaginar la progtwigción sin una stack de llamadas. Eso es algo que se había hecho durante décadas hasta que el uso de un callstack se hizo popular. Las versiones anteriores de FORTRAN carecían de una stack de llamadas y funcionaban muy bien.

Por cierto, existen lenguajes completos de Turing que solo implementan la recursión (por ejemplo, SML) como un medio de bucle. También existen lenguajes completos de Turing que solo implementan la iteración como un medio de bucle (por ejemplo, FORTRAN IV). La tesis de Church-Turing demuestra que cualquier cosa posible en un lenguaje de recursividad solo se puede hacer en un lenguaje no recursivo y vica-versa por el hecho de que ambos tienen la propiedad de turing-completitud.

Aquí hay un algoritmo iterativo:

 def howmany(x,y) a = {} for n in (0..x+y) for m in (0..n) a[[m,nm]] = if m==0 or nm==0 then 1 else a[[m-1,nm]] + a[[m,nm-1]] end end end return a[[x,y]] end 

Una pregunta: si como primera función la función hace una copia de sí misma en un espacio de memoria vacío al azar, y luego, en lugar de llamarse llamar a la copia, ¿sigue siendo esta recurrencia? (1) Yo diría que sí.

¿El uso explícito de stack es una forma real de eliminar la recursión? (2) Yo diría que no. Básicamente, ¿no estamos imitando lo que sucede cuando usamos recursión explícita? Creo que no podemos definir la recursión simplemente como “una función que se llama a sí misma”, ya que veo la recursión también en el “código de copia” (1) y en el “uso explícito de la stack” (2).

Además, no veo cómo el CT demuestra que todos los algoritmos recursivos pueden volverse iterativos. Solo parece decirme que “todo” que tiene el “poder” de la máquina de Turing puede express todos los algoritmos que esto puede express. Si la máquina de Turing no puede recursividad, estamos seguros de que cada recurso recursivo tiene su traducción interativa … ¿La máquina de Turing puede recurrir? Según yo, si se puede “implementar” (por cualquier medio), entonces podemos decir que lo tiene. ¿Lo tiene? No lo sé.

Todas las CPU reales que conozco pueden ser recursivas. Honestamente, no puedo ver cómo progtwigr de verdad sin tener una stack de llamadas, y creo que esto es lo que hace que la recursión sea posible primero.

Evitando la copia (1) y la “stack imitada” (2), ¿hemos demostrado que cada algoritmo recursivo puede expressse iterativamente en máquinas reales? No puedo ver dónde lo demostramos.