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

181

Un hilo de reddit planteó una pregunta aparentemente interesante:

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

El ejemplo (¿contador?) 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))
Tordek
fuente
3
No veo cómo esto es un contraejemplo. La técnica de pila funcionará. No será bonito y no voy a escribirlo, pero es factible. Parece que Akdas lo reconoce en su enlace.
Matthew Flaschen
Su (num numérica xy) es solo (x + y) choosex = (x + y)! / (X! Y!), Que no necesita recursividad.
ShreevatsaR
3
Duplicado de: stackoverflow.com/questions/531668
Henk Holterman el
Yo diría que la recursividad es meramente una conveniencia.
e2-e4

Respuestas:

181

¿Siempre puedes convertir una función recursiva en una iterativa? Sí, absolutamente, y la tesis de Church-Turing lo demuestra 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 te dice con precisión cómo hacer la conversión, pero sí dice que definitivamente es posible.

En muchos casos, convertir 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 calcularse mediante 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 el reverso de esta moneda, ciertamente 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 anteriores, ofreciendo así el beneficio de velocidad sin la molestia de decirle a la computadora exactamente qué pasos debe seguir. seguir en el cálculo de una fórmula con una definición recursiva. Dijkstra casi seguramente imaginó tal sistema. Pasó mucho 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 multiprocesamiento están en una liga superior al 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 haya una razón convincente, probablemente no debería convertir (manualmente) 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 nivel súper alto como [ ponerse ropa interior de asbesto ] Esquema, Lisp, Haskell, OCaml, Perl o Pascal. Suponga que las condiciones son tales que necesita una implementación en C o Java. (Quizás sea política.) Entonces, ciertamente, podría tener algunas funciones escritas de forma recursiva, pero que, traducidas literalmente, explotarían su sistema de tiempo de ejecución. Por ejemplo, es posible una recursión de cola infinita en Scheme, pero el mismo idioma causa un problema para los entornos C existentes. Otro ejemplo es el uso de funciones léxicamente anidadas y alcance estático, que Pascal admite pero C no.

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

Ian
fuente
10
¿Todavía no se ha probado Church-Turing?
Liran Orevi el
15
@eyelidlessness: si puede implementar A en B, significa que B tiene al menos tanta potencia como A. Si no puede ejecutar alguna declaración de A en la A-implementación-de-B, entonces no es una implementación. Si A puede implementarse en B y B puede implementarse en A, potencia (A)> = potencia (B) y potencia (B)> = potencia (A). La única solución es potencia (A) == potencia (B).
Tordek el
66
re: 1er párrafo: Estás hablando de equivalencia de modelos de computación, no de la tesis de Church-Turing. La equivalencia fue PROBADA por Church y / o Turing, pero no es la tesis. La tesis es un hecho experimental de que todo lo que es intuitivamente computable es computable en sentido matemático estricto (por máquinas Turing / funciones recursivas, etc.). Podría ser refutado si usando leyes de la física pudiéramos construir algunas computadoras no clásicas que computaran algo que las máquinas de Turing no pueden hacer (por ejemplo, detener el problema). Mientras que la equivalencia es un teorema matemático, y no será refutada.
sdcvvc
77
¿Cómo diablos obtuvo esta respuesta algún voto positivo? Primero combina la integridad de Turing con la tesis de Church-Turing, luego hace un montón de movimientos incorrectos de las manos, mencionando sistemas "avanzados" y soltando la recursión de cola infinita perezosa (que puede hacer en C o en cualquier lenguaje completo de Turing porque ... uh. ¿Alguien sabe lo que significa Turing completo?). Entonces, una conclusión esperanzadora, como si fuera una pregunta sobre Oprah y todo lo que necesita es ser positivo y alentador. Horrible respuesta!
ex0du5
8
¿Y la cuestión de la semántica? De Verdad? Esta es una pregunta sobre las transformaciones sintácticas, y de alguna manera se ha convertido en una excelente manera de nombrar a Dijkstra e implica que sabes algo sobre el cálculo pi. Permítanme aclarar esto: si uno mira la semántica denotacional de un lenguaje o algún otro modelo no tendrá relación con la respuesta a esta pregunta. Si el lenguaje es ensamblador o un lenguaje de modelado de dominio generativo no significa nada. Se trata solo de la integridad de Turing y la transformación de "variables de pila" en "una pila de variables".
ex0du5
43

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

Si. Una prueba formal simple es mostrar que tanto la recursividad µ como un cálculo no recursivo como GOTO están completos en Turing. 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í hay una:

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

  • HALT, que detiene la ejecución
  • r = r + 1donde rhay algún registro
  • r = r – 1donde rhay algún registro
  • GOTO xdonde xhay una etiqueta
  • IF r ≠ 0 GOTO xdonde rhay algún registro y xes 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 por la reinstalación manual sin sentido de la pila de llamadas).

Para más información ver esta respuesta .

Konrad Rudolph
fuente
¡Gran respuesta! Sin embargo, en la práctica tengo grandes dificultades para convertir algos recursivos en iterativos. Por ejemplo, hasta ahora no pude convertir el típer monomórfico presentado aquí community.topcoder.com/… en un algoritmo iterativo
Nils
31

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

Vinko Vrsalovic
fuente
13

Básicamente, sí, en esencia lo que tiene 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 realizado 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 estado podría usarse para todos los escenarios simulando básicamente las llamadas a métodos. En general, no es posible decir si esto va a ser "mejor" (ya sea más rápido o más eficiente en algún sentido).

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

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

  • El primer recorrido en profundidad se puede hacer usando una pila, el recorrido en primer lugar 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 al ejecutar un solo bucle:

  1. buscar una instrucción,
  2. evaluarlo
  3. ir a 1.
Khaled.K
fuente
7

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

dfa
fuente
17
No diría que siempre es más agradable de leer. Tanto la iteración como la recursión tienen su lugar.
Matthew Flaschen
6

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.

Heinzi
fuente
¿Cuál de los dos anula el propósito si su estructura de datos de la pila está asignada en la pila, o tarda mucho más si está asignada en el montón, no? Eso suena trivial pero ineficiente para mí.
conradkleinespel
1
@conradk En algunos casos, es lo práctico si debe realizar una operación recursiva en árbol en un problema que es lo suficientemente grande como para agotar la pila de llamadas; La memoria de almacenamiento dinámico suele ser mucho más abundante.
jamesdlin
4

En principio, siempre es posible eliminar la recursividad y reemplazarla con una iteración en un lenguaje que tenga 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 es limitada pero donde la cantidad de pila de llamadas que se puede usar no tiene límites (C de 32 bits donde la dirección de las variables de la pila no es accesible). En este caso, la recursividad 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 .

Zayenz
fuente
2

Turing Machines puede calcular todas las funciones computables y, por lo tanto, los sistemas recursivos y las máquinas Turing (sistemas iterativos) son equivalentes.

TRABAJO
fuente
1

A veces, reemplazar la recursividad es mucho más fácil que eso. La recursión solía ser la moda que se enseñaba en CS en la década de 1990, por lo que muchos desarrolladores promedio de esa época pensaron que si resolvías algo con recursividad, era una mejor solución. Por lo tanto, usarían la recursión en lugar de recorrer hacia atrás para revertir el orden, o cosas tontas como esa. Entonces, a veces, eliminar la recursión es un tipo de ejercicio "duh, eso era obvio".

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

Matthias Wandel
fuente
0

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

Los siguientes casos se encuentran entre los fáciles:

Nick Dandoulakis
fuente
0

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 de función que de otro modo habría realizado. Luego, la función de inicio (trampolín) invoca los cierres devueltos hasta que se alcanza el resultado final.

Este enfoque funciona para funciones recursivas mutuas, pero me temo que solo funciona para llamadas de cola.

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

Chris Vest
fuente
0

Yo diría que sí, una llamada a la función no es más que un goto y una operación de pila (más o menos). Todo lo que necesita hacer es imitar la pila que se construye al invocar funciones y hacer algo similar a un goto (puede imitar gotos con idiomas que tampoco tienen explícitamente esta palabra clave).

sfussenegger
fuente
1
Creo que el OP está buscando una prueba u otra cosa sustantiva
Tim
0

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

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 .

Alberto Zaccagni
fuente
-1

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

Con eso en mente, casi todo lo que dices no tiene sentido. 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 una pila de llamadas se hizo popular. Las versiones anteriores de FORTRAN carecían de una pila de llamadas y funcionaban bien.

Por cierto, existen lenguajes completos de Turing que solo implementan la recursividad (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 todo lo posible en un lenguaje de recursión solo se puede hacer en un lenguaje no recursivo y viceversa por el hecho de que ambos tienen la propiedad de la integridad de Turing.

Ricardo
fuente
-3

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
Jules
fuente