Eliminar la recursividad: una mirada a la teoría detrás de escena

10

Soy nuevo en este sitio y esta pregunta ciertamente no tiene un nivel de investigación, pero bueno. Tengo un poco de experiencia en ingeniería de software y casi ninguno en CSTheory, pero me parece atractivo. Para resumir, quisiera una respuesta más detallada a lo siguiente si esta pregunta es aceptable en este sitio.

Entonces, sé que cada programa recursivo tiene un análogo iterativo y entiendo la explicación popular que se le ofrece al mantener algo similar a la "pila del sistema" y presionar la configuración del entorno como la dirección de retorno, etc. Encuentro este tipo de manual .

Siendo un poco más concreto, me gustaría ver (formalmente) cómo se prueba esta afirmación en los casos en que tiene una función que invoca la cadena . Además, ¿qué pasa si hay algunas declaraciones condicionales que podrían hacer que un llame a algún ? Es decir, el gráfico de llamada de función potencial tiene algunos componentes fuertemente conectados. $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$ $F_i$ $F_j$

Me gustaría saber cómo se pueden manejar estas situaciones, digamos un convertidor recursivo a iterativo. ¿Y la descripción manual que mencioné anteriormente es realmente suficiente para este problema? Quiero decir, entonces, ¿por qué es fácil eliminar la recursión en algunos casos? En particular, eliminar la recursividad del recorrido previo al pedido de un árbol binario es realmente fácil: es una pregunta estándar de la entrevista, pero eliminar la recurrencia en el caso de un pedido posterior siempre ha sido una pesadilla para mí.

Lo que realmente estoy preguntando son preguntas $2$

(1) ¿Existe realmente una prueba más formal (convincente?) De que la recursión se puede convertir en iteración?

(2) Si esta teoría está realmente ahí afuera, entonces ¿por qué es que encuentro, por ejemplo, iterar preordenar más fácilmente y postorder tan difícil? (aparte de mi inteligencia limitada)

pl.programming-languages recursion recursive Itachi Uchiha
fuente

1

como la palabra iterando :)

Akash Kumar

No estoy seguro si entiendo completamente, pero si la recursión termina en algún lugar, entonces puedes simular una pila del sistema usando tu propia pila. Para la parte (2), los problemas no son diferentes en términos de complejidad computacional.

singhsumit

Creo que esta pregunta habría sido más adecuada para el sitio de informática que aún no está en vivo. En cuanto a su segunda pregunta, ¿puede explicar por qué cree que es más difícil? El proceso debería ser casi idéntico.

Raphael

Gracias a todos por sus comentarios. Supongo que tengo bastante lectura que hacer.

Itachi Uchiha

@Raphael: un comentario sobre por qué creo que iterar el postorder es difícil (además de que no puedo hacerlo). Estaba leyendo algunos artículos sobre cómo eliminar la recursión y me encontré con algo llamado funciones recursivas de cola. Resulta que son más fáciles de iterar. Todavía no entiendo formalmente por qué es esto cierto; Pero hay otra cosa que debo agregar. He oído que el postorder iterativo requiere dos pilas y no una, pero no conozco los detalles. Y ahora estoy perdido, ¿por qué esta diferencia entre estos dos modos transversales? ¿Y por qué la recursión de la cola es fácil de manejar?

Itachi Uchiha

6

Si lo entiendo correctamente, tiene claro acerca de la conversión de funciones que no contienen otras llamadas a funciones sino a sí mismas.

Así que supongamos que tenemos una "cadena llamada" . Si además suponemos que no son recursivos en sí mismos (porque ya los hemos convertido), podemos incluir todas esas llamadas en la definición de que se convierte en una función recursiva directa con la que ya podemos tratar. $F \to F_1 \to \dots \to F_n \to F$ $F_1, \dots, F_n$ $F$

Esto falla si alguna tiene una cadena de llamada recursiva en la que ocurre , es decir, . En este caso, tenemos una recursión mutua que requiere otro truco para deshacerse. La idea es calcular ambas funciones simultáneamente. Por ejemplo, en el caso trivial: $F_j$ $F$ $F_j \to \dots \to F \to \dots \to F_j$

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

con f'y g'funciones no recursivas (o al menos independientes de fy g) se convierte en

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

Esto naturalmente se extiende a más funciones involucradas y funciones más complicadas.

Rafael
fuente

Me alegro de poder ayudar. Recuerde aceptar su respuesta favorita haciendo clic en la marca de verificación junto a ella.

Raphael

1

Raphel, tu truco funciona solo cuando ambas funciones recursivas aceptan argumentos del mismo tipo. Si fy gacepta diferentes tipos de tipos, se necesita un truco más general.

Andrej Bauer

@AndrejBauer buena observación, lo extrañé totalmente. Realmente me gustó el enfoque de Rafael, pero como observó en casos generales, probablemente necesitemos una idea diferente. ¿Puedes hacer alguna otra sugerencia?

Itachi Uchiha

fg

n - 1

$n-1$

n - 2

$n-2$

Bueno, mira mi respuesta sobre cómo hacerlo.

Andrej Bauer

8

Sí, hay razones convincentes para creer que la recursión puede convertirse en iteración. Esto es lo que hace cada compilador cuando traduce el código fuente al lenguaje máquina. Para la teoría, debe seguir las sugerencias de Dave Clarke. Si desea ver el código real que convierte la recursividad a código no recursivo, eche un vistazo machine.mlen el lenguaje MiniML en mi PL Zoo (observe que la loopfunción en la parte inferior, que realmente ejecuta código, es recursiva de cola y así puede ser trivialmente convertido a un bucle real).

Una cosa más. MiniML no admite funciones recursivas mutuas. Pero esto no es un problema. Si tiene recursividad mutua entre funciones

F_{1} : {UNA}_{1} \to {si}_{1}

$f_1 : A_1 \to B_1$

F_{2} : {UNA}_{2} \to {si}_{2}

$f_2 : A_2 \to B_2$

⋮

$\vdots$

F_{norte} : {UNA}_{norte} \to {si}_{norte}

$f_n : A_n \to B_n$

la recursividad puede expresarse en términos de un solo mapa recursivo

F : {UNA}_{1} + \dots + {UNA}_{norte} \to {si}_{1} + \dots + {si}_{norte},

$f : A_1 + \cdots + A_n \to B_1 + \cdots + B_n,$

Andrej Bauer
fuente

8

Es posible que desee mirar la máquina SECD . Un lenguaje funcional (aunque podría ser cualquier idioma) se traduce en una serie de instrucciones que manejan cosas como poner argumentos de pilas, "invocar" nuevas funciones, etc., todo administrado por un simple ciclo.
Las llamadas recursivas nunca se invocan realmente. En cambio, las instrucciones del cuerpo de la función que se llama se coloca en la pila para ejecutar.

Un enfoque relacionado es la máquina CEK .

Ambos han existido durante mucho tiempo, por lo que hay mucho trabajo sobre ellos. Y, por supuesto, hay pruebas de que funcionan y el procedimiento para "compilar" un programa en instrucciones SECD es lineal en el tamaño del programa (no tiene que pensar en el programa).

El punto de mi respuesta es que hay un procedimiento automático para hacer lo que quieres. Desafortunadamente, la transformación no será necesariamente en términos de cosas que son inmediatamente fáciles de interpretar para un programador. Creo que la clave es que cuando desea iterizar un programa, necesita almacenar en la pila lo que el programa debe hacer cuando regresa de una llamada de función iterizada (esto se llama continuación). Para algunas funciones (como las funciones recursivas de cola) la continuación es trivial. Para otros, la continuación puede ser muy compleja, especialmente si tiene que codificarla usted mismo.

Dave Clarke
fuente

Seré honesto aquí. Realmente quiero entender por qué (y cómo) puedes iterar cada programa recursivo. Pero me resulta difícil leer un periódico, por lo general no son accesibles para mí. Quiero decir, quiero una razón más profunda que la descripción "manual" de la que hablé en la pregunta. pero también estoy contento con algo que me da una nueva visión: no tiene que ser la prueba completa en sus detalles esenciales

Itachi Uchiha

[cntd] Quiero decir que me gustaría que la prueba, si hay una, me diga por qué iterar un programa es más fácil que el otro. Pero, en cierto sentido, el convertidor recursivo a iterativo debería funcionar sin importar qué programa recursivo tome como entrada. No estoy seguro, pero supongo que hacer un convertidor de este tipo podría ser tan difícil como el problema de detención. Solo estoy adivinando aquí, pero me encantaría que exista un convertidor recursivo a iterativo y, si lo hace, me gustaría que explique la complejidad inherente de iterar diferentes programas recursivos. No estoy seguro, pero ¿debería editar la pregunta? ¿Está clara mi pregunta?

Itachi Uchiha

@ItachiUchiha: no creo que su problema sea indecidible. Mira la respuesta de Andrej Bauer. Señala que cada compilador lo hace cuando traduce el código fuente al lenguaje máquina. También agrega que puede ver el código real que convierte recursivo a no recursivo en el lenguaje MiniM (a) l. Esto indica claramente que hay un procedimiento de decisión para "iterar" la recursividad. No estoy seguro sobre la dificultad / complejidad inherente (conceptual) de eliminar la recursividad. No entiendo esta pregunta muy claramente, pero parece interesante. Tal vez pueda editar su pregunta para obtener una mejor respuesta

Akash Kumar

El punto de mi respuesta es que hay un procedimiento automático para hacer lo que quieres. Desafortunadamente, la transformación no será necesariamente en términos de cosas que son inmediatamente fáciles de interpretar para un programador. Creo que la clave es que cuando desea iterizar un programa, necesita almacenar en la pila lo que el programa debe hacer cuando regresa de una llamada de función iterizada (esto se llama continuación). Para algunas funciones (como las funciones recursivas de cola) la continuación es trivial. Para otros, la continuación puede ser muy compleja, especialmente si tiene que codificarla usted mismo.

Dave Clarke

6

P : "¿Existe realmente una prueba más formal (convincente) de que la recursión se puede convertir en iteración?"

A : La integridad de Turing de una máquina de Turing :-)

Bromas aparte, el modelo de máquina del programa almacenado de acceso aleatorio (RASP) equivalente de Turing está cerca de cómo funcionan los microprocesadores reales y su conjunto de instrucciones contiene solo un salto condicional (sin recursión). La posibilidad de modificar dinámicamente el código hace que la tarea de implementar subrutinas y llamadas recursivas sea más fácil.

Creo que puede encontrar muchos artículos / artículos sobre la " conversión recursiva a iterativa " (vea la respuesta de Dave o simplemente Google las palabras clave), pero quizás un enfoque menos conocido (y práctico ) es la investigación más reciente sobre la implementación de hardware de algoritmos recursivos ( usando el lenguaje VHDL que se "compila" directamente en una pieza de hardware). Por ejemplo, ver el artículo de V.Sklyarov " Implementación basada en FPGA de algoritmos recursivos " ( El artículo sugiere un método novedoso para implementar algoritmos recursivos en hardware ... Se han estudiado dos aplicaciones prácticas de algoritmos recursivos en el área de clasificación y compresión de datos en detalle .... ).

Marzio De Biasi
fuente

1

Si está familiarizado con los idiomas que admiten lambdas, entonces una vía es investigar la transformación de CPS. Eliminar el uso de la pila de llamadas (y la recursividad en particular) es exactamente lo que hace la transformación CPS. Transforma un programa que contiene llamadas de procedimiento en un programa con solo llamadas de cola (puede pensar en ellas como gotos, que es una construcción iterativa).

La transformación CPS está estrechamente relacionada con el mantenimiento explícito de una pila de llamadas en una pila basada en una matriz tradicional, pero en lugar de en una matriz, la pila de llamadas se representa con cierres vinculados.

Jules
fuente

0

En mi opinión, esta pregunta se remonta a los orígenes de las definiciones de computación y hace mucho tiempo se demostró rigurosamente en esa época cuando el cálculo lambda de la iglesia (que captura el concepto de recursión) demostró ser equivalente a las máquinas de Turing, y está contenido en la terminología aún utilizada "lenguajes / funciones recursivas". También, aparentemente, una referencia clave posterior a lo largo de estas líneas es la siguiente

Como se señala en el artículo de 1965 de Peter Landin, A Correspondence entre ALGOL 60 y la notación Lambda de Church, los lenguajes secuenciales de programación procesal se pueden entender en términos del cálculo lambda, que proporciona los mecanismos básicos para la abstracción procesal y la aplicación del procedimiento (subprograma).

Gran parte del bkd sobre esto está en esta tesis de la iglesia de la página de Wikipedia . No estoy seguro de los detalles exactos, pero el artículo de Wikipedia parece indicar que fue Rosser (1939) quien primero probó esta equivalencia entre el cálculo lambda y las máquinas de Turing. ¿quizás / presumiblemente su artículo tiene un mecanismo en forma de pila para convertir las llamadas lambda (posiblemente recursivas) a la construcción tm?

Rosser, JB (1939). "Una exposición informal de pruebas del teorema de Godel y el teorema de la iglesia". The Journal of Symbolic Logic (The Journal of Symbolic Logic, Vol. 4, Núm. 2) 4 (2): 53–60. doi: 10.2307 / 2269059. JSTOR 2269059.

Nota, por supuesto, para cualquier persona interesada en los principios, el lenguaje Lisp moderno y el Esquema variante tienen una fuerte semejanza con el cálculo lambda. El estudio del código del intérprete para la evaluación de expresiones conduce a ideas que originalmente estaban contenidas en documentos para la integridad del cálculo lambda.

vzn
fuente

1

La prueba de equivalencia de Turing / lambda se encuentra en el apéndice de este documento: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Radu GRIGore

Eliminar la recursividad: una mirada a la teoría detrás de escena

Respuestas: