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

Question

A hilo rojo planteó una pregunta aparentemente interesante:

Las funciones recursivas de cola se pueden convertir trivialmente en funciones iterativas.Otros se pueden transformar utilizando una pila explícita.Poder cada ¿La recursión se transforma en iteración?

El (¿contra?)ejemplo en la publicación es el par:

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

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Answer 1

Puede usted gire siempre una función recursiva en un proceso iterativo? Sí, por supuesto, y la tesis de Church-Turing demuestra que si mal no recuerdo. En términos simples, se afirma 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 es definitivamente posible.

En muchos casos, la conversión de una función recursiva es fácil. Knuth ofrece varias técnicas en "The Art of Computer Programming". Y, a menudo, una cosa calculada de forma recursiva puede ser calculado por un enfoque completamente diferente en menos tiempo y en el espacio. El ejemplo clásico de esto es los números de Fibonacci o secuencias de los mismos. Seguramente has conocido a este problema en su plan de estudios.

En la otra cara de la moneda, sin duda podemos imaginar un sistema de programación tan avanzado como para el tratamiento de una definición recursiva de una fórmula como una invitación a memoize resultados anteriores, lo que ofrece la ventaja de velocidad, sin la molestia de decirle a la computadora exactamente que los pasos a seguir en el cálculo de una fórmula con una definición recursiva. Dijkstra es casi seguro que se imaginaba un sistema de este tipo. Pasó mucho tiempo tratando de separar la aplicación de la semántica de un lenguaje de programación. Por otra parte, sus lenguajes de programación no deterministas y multiprocesamiento están en una liga por encima del programador profesional practicante.

En el análisis final, muchas funciones son simplemente más fácil de entender, leer y escribir en forma recursiva. A menos que haya una razón de peso, probablemente no debería (manualmente) convertir estas funciones a un algoritmo iterativo de forma explícita. El ordenador se encargará de que el trabajo correctamente.

Puedo ver una razón de peso. Supongamos que usted tiene un sistema prototipo en un lenguaje de alto nivel de super-alta como [ ponerse la ropa interior de amianto ] Esquema, Lisp, Haskell, OCaml, Perl, o Pascal. Supongamos que las condiciones son tales que se necesita una aplicación en C o Java. (Tal vez sea la política.) A continuación, ciertamente se podría tener algunas funciones escriben de forma recursiva, pero que, traducido literalmente, podría explotar su sistema de tiempo de ejecución. Por ejemplo, infinito recursión de cola es posible en el Esquema, pero el mismo lenguaje provoca un problema para entornos C existentes. Otro ejemplo es el uso de funciones léxico anidados y el alcance estática, que Pascal apoya pero C no lo hace.

En estas circunstancias, es posible tratar de superar la resistencia política a la lengua original. Usted podría encontrarse reimplementar Lisp mal, como en la ley de la décima parte (la lengua en la mejilla) Greenspun. O que sólo podría encontrar un enfoque completamente diferente a la solución. Pero en cualquier caso, seguramente hay una manera.

Answer 2

¿Siempre es posible escribir una forma no recursiva para cada función recursiva?

Sí.Una prueba formal simple es demostrar que ambos µ recursividad y un cálculo no recursivo como GOTO son ambos Turing completos.Dado que 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 recursivo completo de Turing.

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

Un programa GOTO es una secuencia de comandos PAG ejecutado en un máquina de registro tal que PAG es uno de los siguientes:

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

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

Para más información ver esta respuesta.

Answer 3

recursión se implementa como pilas o construcciones similares en los intérpretes o compiladores reales. Así que sin duda puede convertir una función recursiva para una contraparte iterativo porque eso es lo que ha hecho siempre (si automáticamente) . Usted acaba de ser duplicar el trabajo del compilador en una red ad-hoc y, probablemente, de una manera muy fea y poco eficiente.

Answer 4

Básicamente sí, en esencia, lo que al final tener que hacer es sustituir las llamadas de método (que implícitamente empujan estado en la pila) en la pila explícita empuja a recordar dónde la 'llamada anterior' se había levantado a, y luego ejecutar el ' llamado método' en su lugar.

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

Answer 5

• flujo de ejecución función recursiva puede ser representada como un árbol.

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

• recorrido en profundidad se puede hacer usando una pila, de recorrido primero en amplitud se puede hacer usando una cola.

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

.

  

Puede cualquier recursividad puede hacer en un solo bucle? Sí, porque

     

una máquina de Turing hace todo lo hace mediante la ejecución de un solo bucle:

     

  
1. extraer una instrucción,
  
2. evaluarlo,
  
3. Goto 1.
  

Answer 6

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

Answer 7

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

Answer 8

En principio, siempre es posible eliminar la recursividad y sustituirla por iteración en un idioma que tiene estado infinito tanto para estructuras de datos y para la pila de llamadas. Esto es una consecuencia básica de la tesis de Church-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 está limitado pero donde la cantidad de pila de llamadas que se puede utilizar es ilimitado (32-bit C en la dirección de las variables de pila no es accesible). En este caso, la repetición es más poderoso simplemente porque tiene más memoria que puede utilizar; no hay suficiente memoria explícita asignable para emular la pila de llamadas. Para una discusión detallada sobre este tema, consulte discusión.

Answer 9

A veces la sustitución de la recursividad es mucho más fácil que eso. Recursividad solía ser la cosa moda enseña en CS en la década de 1990, y por lo que una gran cantidad de desarrolladores promedio desde ese momento pensé que si usted ha resuelto algo con la recursividad, que era una mejor solución. Así que usarían la recursividad en lugar de un bucle hacia atrás a fin, o cosas tontas como que revertir. Así que a veces la eliminación de la recursividad es un simple "duh, eso era evidente" tipo de ejercicio.

Este es un problema menor ahora, como la moda se ha desplazado hacia otras tecnologías.

Answer 10

Todas las funciones computables se pueden calcular por máquinas de Turing y por lo tanto los sistemas recursivos y máquinas de Turing (sistemas iterativos) son equivalentes.

Answer 11

La eliminación de la recursividad es un problema complejo y es factible en circunstancias bien definidas.

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

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

Answer 12

Appart de la pila explícita, otro patrón para la conversión de recursión en iteración es con el uso de un trampolín.

A continuación, las funciones o bien devolver el resultado final o un cierre de la llamada a la función que de otro modo se habría realizado. Entonces, la función de iniciación (trampolín) mantener la invocación de los cierres devueltos hasta que se alcanza el resultado final.

Este enfoque funciona para funciones mutuamente recursivas, pero me temo que sólo funciona para las llamadas traseras.

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

Answer 13

Yo diría que sí - una llamada de 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 a la pila que se construye al invocar funciones y hacer algo similar como Goto (puede imitar GOTOS con idiomas que no tienen explícitamente esta palabra clave también).

Answer 14

Tener un vistazo a las siguientes entradas en la Wikipedia, puede utilizarlos 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 de por dónde empezar:

  

Solución de una relación de recurrencia significa la obtención de una de forma cerrada solución : un no función recursiva de n.

También eche un vistazo en el último párrafo del esta entrada .

Answer 15

  

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

Más detalles: https://developer.mozilla.org / es-eS / docs / web / JavaScript / Guía / Funciones

Answer 16

tazzego, recursividad significa que una función llamará a sí mismo, le guste o no. Cuando la gente habla acerca de si o no las cosas pueden hacerse sin recursividad, que quieren decir esto y no se puede decir "no, eso no es cierto, porque no estoy de acuerdo con la definición de la recursividad" como una declaración válida.

Con esto en mente, casi todo lo demás que usted dice no tiene sentido. La única otra cosa que usted dice que no tiene ningún sentido es la idea de que no se puede imaginar programación sin una pila de llamadas. Eso es algo que se había hecho durante décadas, hasta el uso de un pila de llamadas se hizo popular. Las versiones antiguas de FORTRAN carecían de una pila de llamadas y que funcionaba bien.

Por cierto, existen lenguajes de Turing-completo que sólo implementan la recursividad (por ejemplo SML) como medio de bucle. También existen idiomas Turing completo que sólo implementan iteración como un medio de bucle (por ejemplo FORTRAN IV). La tesis de Church-Turing demuestra que todo es posible en unas lenguas de recursividad sólo puede hacerse en un lenguaje no recursivo y vica versa por el hecho de que ambos tienen la propiedad de Turing-completo.

Answer 17

Este es 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