language-agnostic - usar - recursividad ventajas

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

Question

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 pila explícita. ¿Puede cada recursión transformarse en iteración?

El (contador?) 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

¿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 programa 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 pila de llamadas).

Answer 2

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 pila. De hecho, la recursividad usa una pila: la pila de funciones.

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

Answer 3

¿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 programació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 programació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 programación. Por otra parte, sus lenguajes de programación no deterministas y de multiprocesamiento están en una liga por encima del programador 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 alcance 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.

Answer 4

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.

Answer 5

Además 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 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)

Answer 6

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

Answer 7

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 pila) en apilamientos de pila 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 pila 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.

Answer 8

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 .

Answer 9

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

Answer 10

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 pila de llamadas. Esta 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 bastante posible tener un lenguaje donde la cantidad de memoria que se puede asignar en el programa sea limitada, pero donde la cantidad de la pila de llamadas que se puede usar no esté limitada (C de 32 bits donde la dirección de las variables de la 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 .

Answer 11

La recursión se implementa como pilas o construcciones similares en los intérpretes o compiladores 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 compilador de una manera ad-hoc y probablemente de una manera muy fea e ineficiente.

Answer 12

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.

Answer 13

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

Answer 14

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.

Answer 15

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 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 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 programar de verdad sin tener una pila de llamadas, y creo que esto es lo que hace que la recursión sea posible primero.

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

Answer 16

Yo diría que sí, una llamada a función no es más que una operación de ir y una pila (hablando en términos generales). Todo lo que necesita hacer es imitar la pila 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).

Answer 17

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 declaració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 anteriores de FORTRAN carecían de una pila 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.

Answer 18

• 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 pila, el recorrido de ancho se puede hacer usando una cola.

Entonces, la respuesta es: sí. Por qué: https://.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.