La iteración puede reemplazar la recursividad?

42

He estado viendo todo el desbordamiento de la pila, por ejemplo, aquí , aquí , aquí , aquí , aquí y algunos otros que no me importa mencionar, que "cualquier programa que use la recursión puede convertirse en un programa usando solo la iteración".

Incluso hubo un hilo muy votado con una respuesta muy votada que decía que sí, que es posible.

Ahora no digo que estén equivocados. Es solo que esa respuesta contrarresta mi escaso conocimiento y comprensión sobre informática.

Creo que cada función iterativa se puede expresar como recursión, y Wikipedia tiene una declaración en ese sentido. Sin embargo, dudo que lo contrario sea cierto. Por un lado, dudo que las funciones recursivas no primitivas se puedan expresar de forma iterativa.

También dudo que las hiperoperaciones se puedan expresar de forma iterativa.

En su respuesta (que no entiendo por cierto) a mi pregunta, @YuvalFIlmus dijo que no es posible convertir ninguna secuencia de operaciones matemáticas en una secuencia de adiciones.

Si la respuesta de YF es correcta (supongo que sí, pero su razonamiento estaba por encima de mi cabeza), ¿no significa esto que no todas las recursiones pueden convertirse en iteraciones? Porque si fuera posible convertir cada recursión en iteración, podría expresar todas las operaciones como una secuencia de adiciones.

Mi pregunta es esta:

¿Se puede convertir cada recursión en iteración y por qué?

Por favor, responda un estudiante de secundaria brillante o un estudiante de primer año lo entenderá. Gracias.

PD: No sé qué es primitivo recursivo (sí sé acerca de la función de Ackermann, y que no es primitivo recursivo, pero aún es computable. Todo mi conocimiento proviene de la página de Wikipedia sobre la función de Ackermann).

PPS: Si la respuesta es sí, ¿podría, por ejemplo, escribir una versión iterativa de una función recursiva no primitiva. Por ejemplo, Ackermann en la respuesta. Me ayudará a entender.

Tobi Alafin
fuente
21
Todo lo que ejecuta en una CPU es iterativo. Puede escribirlo recursivamente en un lenguaje de orden superior, pero de todos modos se compila en un montón de instrucciones de ensamblador iterativo. Así que, literalmente, el compilador hace exactamente lo que está pidiendo: convierte toda su recurrencia sofisticada en un montón de instrucciones iterativas para una CPU.
Davor
66
En un nivel bajo, la mayoría de nosotros sabemos que la recursión es igual a la iteración más la pila. Las gramáticas sin contexto modelan la recursividad, mientras que los autómatas pushdown son "programas" iterativos con memoria de pila.
Hendrik Jan
2
Simplemente señalando que generalmente es una buena idea esperar al menos 24 horas para ver si aparecen otras respuestas. La pregunta aceptada parece demasiado larga y complicada para mí, francamente, y parece complicar deliberadamente las cosas más de lo necesario. La respuesta básica a su pregunta es "la pila utilizada para la recursión puede implementarse explícitamente de forma iterativa", y no necesita ser mucho más complicada que eso. Las consideraciones acerca de que la memoria sea ilimitada o no no entran en juego, ya que esa característica también es necesaria para las pilas de recursión.
AnoE
es posible implementar el emulador de máquina de Turing con solo iteración
Sarge Borsch
En una clase de idiomas comparativos que tomé hace mucho tiempo, tuvimos que escribir la función de Ackermann en ensamblador, en FORTRAN (no Fortran moderno) y en un lenguaje recursivo de elección. Entonces sí, es posible en la práctica. Y, por supuesto, es posible en teoría. Véase, por ejemplo, la pregunta que prueba que las máquinas de Turing y el cálculo lambda son equivalentes .
David Hammen

Respuestas:

52

Es posible reemplazar la recursión por iteración más memoria ilimitada .

Si solo tiene iteración (digamos, bucles while) y una cantidad finita de memoria, entonces todo lo que tiene es un autómata finito. Con una cantidad finita de memoria, el cálculo tiene un número finito de pasos posibles, por lo que es posible simularlos a todos con un autómata finito.

Tener memoria ilimitada cambia el trato. Esta memoria ilimitada puede tomar muchas formas que resultan tener un poder expresivo equivalente. Por ejemplo, una máquina Turing lo mantiene simple: hay una sola cinta, y la computadora solo puede avanzar o retroceder en la cinta paso a paso, pero eso es suficiente para hacer cualquier cosa que pueda hacer con las funciones recursivas.

Una máquina de Turing puede verse como un modelo idealizado de una computadora (máquina de estados finitos) con algo de almacenamiento adicional que crece bajo demanda. Tenga en cuenta que es crucial que no solo no haya un límite finito en la cinta, sino que incluso dada la entrada, no puede predecir de manera confiable cuánta cinta se necesitará. Si pudiera predecir (es decir, calcular) cuánta cinta se necesita a partir de la entrada, entonces podría decidir si la computación se detendría calculando el tamaño máximo de la cinta y luego tratando todo el sistema, incluida la cinta ahora finita, como una máquina de estados finitos .

Otra forma de simular una máquina Turing con computadoras es la siguiente. Simule la máquina Turing con un programa de computadora que almacena el comienzo de la cinta en la memoria. Si el cálculo llega al final de la parte de la cinta que cabe en la memoria, reemplace la computadora por una computadora más grande y vuelva a ejecutar el cálculo.

Ahora suponga que desea simular un cálculo recursivo con una computadora. Las técnicas para ejecutar funciones recursivas son bien conocidas: cada llamada a la función tiene una pieza de memoria, llamada marco de pila . De manera crucial, las funciones recursivas pueden propagar información a través de múltiples llamadas al pasar variables. En términos de implementación en una computadora, eso significa que una llamada de función podría acceder al marco de la pila de una llamada (grand-) * parent.

Una computadora es un procesador, una máquina de estados finitos (con una gran cantidad de estados, pero aquí estamos haciendo la teoría de la computación, por lo que todo lo que importa es que es finita), junto con una memoria finita. El microprocesador ejecuta un bucle while gigante: "mientras está encendido, lea una instrucción de la memoria y ejecútela". (Los procesadores reales son mucho más complejos que eso, pero no afecta lo que pueden calcular, solo lo rápido y conveniente que lo hacen). Una computadora puede ejecutar funciones recursivas con solo este ciclo while para proporcionar iteración, más el mecanismo para acceder a la memoria, incluida la capacidad de aumentar el tamaño de la memoria a voluntad.

Si restringe la recursividad a la recursividad primitiva, puede restringir la iteración a la iteración acotada . Es decir, en lugar de usar bucles while con un tiempo de ejecución impredecible, puede usar bucles donde el número de iteraciones se conoce al comienzo del bucle¹. El número de iteraciones puede no conocerse al comienzo del programa: puede haber sido calculado por bucles anteriores.

Ni siquiera voy a esbozar una prueba aquí, pero hay una relación intuitiva entre pasar de la recursividad primitiva a la recursividad completa y pasar de bucles a bucles while: en ambos casos, implica no saber de antemano cuándo detener. Con una recursión completa, esto se hace con el operador de minimización, donde continúa hasta que encuentra un parámetro que satisfaga la condición. Con los bucles while, esto se lleva a cabo hasta que se cumpla la condición del bucle.

¹ los bucles en lenguajes tipo C pueden realizar una iteración ilimitada de la misma manera , es solo una cuestión de convención restringirlos a la iteración acotada. Cuando la gente habla de "for loops" en la teoría de la computación, eso significa solo loops que cuentan de 1 a n (o equivalente). forwhilen

Gilles 'SO- deja de ser malvado'
fuente
Aceptando la explicación detallada, mantenida en el nivel solicitado.
Tobi Alafin
12
Creo que vale la pena señalar que en las computadoras reales, la recursión también usa memoria (creciente pila de llamadas). Por lo tanto, en aplicaciones prácticas, no se requiere memoria ilimitada (porque todo está limitado por igual). Y la recursión a menudo necesita más memoria que la iteración.
Agent_L
@Agent_L Sí, la recursión necesita memoria ilimitada para almacenar todos los marcos de la pila. Con un enfoque de recursión, existe un requisito de memoria ilimitada, pero no se puede separar intuitivamente de la secuencia de operaciones como con las iteraciones.
Gilles 'SO- deja de ser malvado'
1
Quizás de interés sería la tesis de Church-Turing. Las máquinas de Turing son máquinas altamente iterativas sin concepto (inherente) de recursión. El cálculo lambda es un lenguaje ideado para expresar cálculos de manera recursiva. La tesis de Church-Turing mostró que todas las expresiones lambda podían evaluarse en una máquina de Turing, vinculando recursividad e iteración.
Cort Ammon
1
@BlackVegetable Si un método recursivo no tiene variables internas, y la única memoria que usa es la pila de llamadas (lo que puede ser optimizado por el TCO), entonces es probable que su versión iterativa tampoco tenga variables internas y use solo una cantidad constante de memoria ( variables) compartidas en todas las iteraciones, como counter.
Agent_L
33

Cada recursión se puede convertir a iteración, como lo atestigua su CPU, que ejecuta programas arbitrarios utilizando una iteración infinita fetch-execute. Esta es una forma del teorema de Böhm-Jacopini . Además, muchos modelos de computación completos de Turing no tienen recursividad, por ejemplo, máquinas de Turing y máquinas de mostrador .

Las funciones recursivas primitivas corresponden a programas que utilizan iteración limitada , es decir, debe especificar el número de iteraciones que se ejecuta un bucle por adelantado. La iteración limitada no puede simular la recursividad en general, ya que la función de Ackermann no es primitiva recursiva. Pero la iteración sin límites puede simular cualquier función parcialmente computable.

Yuval Filmus
fuente
25

a(n,m)

s

push(s,x)xxpop(s)empty(s)

Ackermann(n0,m0):

  • s= vacío (inicializar pila vacía)
  • push(s,n0)
  • push(s,m0)
  • while(true):
    • mpop(s)
    • if(empty(s)):
      • return m (esto finaliza el ciclo)
    • npop(s)
    • if(n=0):
      • push(s,m+1)
    • else if(m=0):
      • push(s,n1)
      • push(s,1)
    • else:
      • push(s,n1)
      • push(s,n)
      • push(s,m1)

Implementé esto en Ceilán, puede ejecutarlo en el WebIDE , si lo desea. (Produce la pila al comienzo de cada iteración del bucle).

Por supuesto, esto simplemente movió la pila de llamadas implícitas de la recursión a una pila explícita con los parámetros y los valores de retorno.

Paŭlo Ebermann
fuente
16
Creo que este es un punto importante. Usted ha demostrado explícitamente que la recursividad no es nada especial y que se puede eliminar simplemente haciendo un seguimiento de la pila de llamadas usted mismo, en lugar de dejar que el compilador lo haga. La recursión es solo una característica del compilador que facilita la escritura de este tipo de programa.
David Richerby
44
Gracias por hacer el esfuerzo de escribir el programa solicitado.
Tobi Alafin
16

Ya hay algunas respuestas geniales (con las que ni siquiera espero competir), pero me gustaría presentar esta explicación simple.

La recursión es solo la manipulación de la pila de tiempo de ejecución. La recurrencia agrega un nuevo marco de pila (para la nueva invocación de la función recursiva), y la devolución elimina un marco de pila (para la innovación recién completada de la función recursiva). La recursión hará que se agreguen / eliminen algunos marcos de pila, hasta que finalmente todos salgan (¡con suerte!) Y el resultado se devuelva a la persona que llama.

Ahora, ¿qué sucedería si hicieras tu propia pila, reemplazaras las llamadas a funciones recursivas con empujar a la pila, reemplazaras las funciones recursivas por hacer estallar la pila, y tuvieras un ciclo while que se ejecutó hasta que la pila estuvo vacía?

Alexander - Restablece a Monica
fuente
2

Por lo que puedo decir, y en mi propia experiencia, puede implementar cualquier recursión como una iteración. Como se mencionó anteriormente, la recursión utiliza la pila, que es conceptualmente ilimitada, pero prácticamente limitada (¿alguna vez ha recibido un mensaje de desbordamiento de pila?). En mis primeros días de programación (en el tercer cuarto del último siglo del último milenio) estaba usando lenguajes no recursivos que implementaban algoritmos recursivos y no tuve problemas. Sin embargo, no estoy seguro de cómo se podría probar.

Louis Giokas
fuente