¿Se puede convertir cada recursión en iteración?

¿Es siempre posible escribir una forma no recursiva para cada función recursiva?

Sí. Una prueba formal simple es demostrar que tanto µ recursion como un cálculo no recursivo como GOTO son Turing completos. Dado que todos los cálculos completos de Turing son estrictamente equivalentes en su poder expresivo, todas las funciones recursivas pueden ser implementadas por el cálculo completo de Turing no recursivo.

Desafortunadamente, no puedo encontrar un buen definición de GOTO online así que aquí hay una:

Un programa GOTO es una secuencia de comandos P ejecutados en una máquina de registro tal que P es una de las 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 las anteriores comando.

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

La recursión se implementa como pilas o construcciones similares en los intérpretes o compiladores reales. Así que ciertamente puedes convertir una función recursiva a una contraparte iterativa porque así es como siempre se hace (si es automáticamente). Simplemente estarás duplicando el trabajo del compilador de manera ad-hoc y probablemente de una manera muy fea e ineficiente.

Básicamente sí, en esencia lo que tienes que hacer es reemplazar las llamadas a métodos (que implícitamente empujan el estado a la pila) en empujes explícitos de la pila para recordar dónde se había llegado a la 'llamada anterior', y luego ejecutar el 'método llamado' en su lugar.

Me imagino que la combinación de un bucle, una pila y una máquina de estado podría usarse para todos los escenarios básicamente simulando las llamadas a los métodos. Si esto va a ser o no 'mejor' (ya sea más rápido, o más eficiente en cierto sentido) no es realmente posible decir en general.

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

• El flujo de ejecución de funciones recursivas se puede representar como un árbol.

• La misma lógica se puede hacer por un bucle, que utiliza una estructura de datos para atravesar ese árbol.

• El recorrido en profundidad primero se puede hacer usando una pila, el recorrido en anchura primero se puede hacer usando una cola.

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

¿Se puede hacer cualquier recursión en un solo bucle? Sí, porque

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

1. obtener una instrucción,
2. evaluarlo,
3. goto 1.

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

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

Dado un lenguaje de programación real, la respuesta no es tan obvia. El problema es que es muy posible tener un lenguaje donde la cantidad de memoria que se puede asignar en el programa es limitada, pero donde la cantidad de pila de llamadas que se puede se usa sin límite (C de 32 bits donde la dirección de las variables de pila 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 pila 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 recursión solía ser la cosa de moda que se enseñaba en CS en la década de 1990, por lo que muchos desarrolladores promedio de ese tiempo pensaron que si resolvías algo con recursión, era una mejor solución. Así que usarían recursión en lugar de bucle hacia atrás para invertir el orden, o cosas tontas como esa. Así que a veces la eliminación de la recursión es un simple" duh, que era obvio " tipo de ejercicio.

Esto es menos de un problema ahora, como el la moda se ha desplazado hacia otras tecnologías.

Todas las funciones computables pueden ser calculadas por Máquinas de Turing 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 bajo circunstancias bien definidas.

Los siguientes casos están entre los fáciles:

• recursión de cola
• recursión lineal directa

Aparte de la pila 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 a la función que de otro modo habría realizado. Luego, la función de inicio (trampolining) 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 de cola.

Http://en.wikipedia.org/wiki/Trampoline_ (computadoras)

Diría que sí - una llamada a una función no es más que un goto y una operación de pila (en términos generales). Todo lo que necesita hacer es imitar la pila que se construye mientras invoca funciones y hacer algo similar como un goto (puede imitar 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.

• Recursión en ciencias de la computación
• Relación de recurrencia

Sigue un párrafo que puede darte alguna pista sobre por dónde empezar:

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

También echar un vistazo a la última párrafo de esta entrada.

Es posible convertir cualquier algoritmo recursivo a un algoritmo no recursivo uno, pero a menudo la lógica es mucho más compleja y hacerlo requiere el uso de una pila. De hecho, la recursión en sí utiliza una pila: pila de funciones.

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

Tazzego, recursión significa que una función se llamará a sí misma te guste o no. Cuando la gente está hablando de si las cosas se pueden hacer o no sin recursión, quieren decir 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 afirmación 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 programación sin una pila 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 antiguas de FORTRAN carecían de un callstack y funcionaban bien.

Por cierto, existen lenguajes Turing-completos que solo implementan recursión (por ejemplo, SML) como un medio de bucle. También existen lenguajes Turing-completos que solo implementan la iteración como un medio de bucle (por ejemplo, FORTRAN IV). La tesis de Church-Turing demuestra que todo lo posible en una recursión-solo los lenguajes se pueden hacer en un lenguaje no recursivo y viceversa 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,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end

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

¿Es el uso explícito de la pila una forma real de eliminar la recursividad? (2) Yo diría que no. Básicamente, ¿no estamos imitando lo que sucede cuando usamos explícitamente la recursión? Creo que no podemos definir recursión simplemente como "una función que se llama a sí misma", ya que veo recursión también en el "código de copia" (1) y en el "uso explícito de pila" (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 expresar todos los algoritmos que esto puede expresar. Si la máquina de Turing no puede recurrir, estamos seguros de que todo algo recursivo tiene su traducción interactiva... La máquina de Turing puede recursión? Según mí, si se puede " implementar "(por cualquier medio), entonces podemos di que lo tiene. ¿Lo ha hecho? No sé.

Todas las CPUs sé que puede recursividad. Honestamente, no puedo ver cómo programar de verdad sin tener una pila de llamadas, y creo que esto es lo que hace posible la recursión primero.

Evitando copiar(1) y "imitated stack"(2), ¿hemos demostrado que todo algo recursivo puede ser, en máquinas reales, expresado iterativamente?! No puedo ver dónde lo demostramos.