¿Se puede convertir cada recursión en iteración?
Un hilo de Reddit 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. ¿ Se puede transformar cada recursión 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))
¿Siempre puedes convertir una función recursiva en iterativa? Sí, absolutamente, y la tesis de Church-Turing lo demuestra si la memoria no me falla. En términos sencillos, afirma que lo que es computable mediante funciones recursivas también lo es mediante un modelo iterativo (como la máquina de Turing) y viceversa. La tesis no dice exactamente cómo hacer la conversión, pero sí dice que definitivamente es posible.
En muchos casos, convertir una función recursiva es sencillo. Knuth ofrece varias técnicas en "El arte de la programación informática". Y, a menudo, algo calculado de forma recursiva 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 te has encontrado con este problema en tu plan de estudios.
En la otra cara de esta moneda, ciertamente podemos imaginar un sistema de programación tan avanzado que trate 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. seguir en el cálculo de una fórmula con una definición recursiva. Es casi seguro que Dijkstra imaginó tal sistema. Pasó mucho tiempo intentando 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 por encima del programador profesional en ejercicio.
En última instancia, 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 realizará ese trabajo correctamente.
Puedo ver una razón convincente. Supongamos que tiene un sistema prototipo en un lenguaje de nivel súper alto como 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 de forma recursiva pero que, traducidas literalmente, explotarían su sistema de ejecución. Por ejemplo, la recursividad de cola infinita es posible en Scheme, pero el mismo modismo causa un problema en los entornos C existentes. Otro ejemplo es el uso de funciones léxicas anidadas y alcance estático, que Pascal admite pero C no.
En estas circunstancias, se podría intentar superar la resistencia política al idioma original. Es posible que se encuentre reimplementando mal Lisp, como en la décima ley (irónica) de Greenspun. O tal vez simplemente encuentre un enfoque de solución completamente diferente. Pero en cualquier caso, seguramente hay una manera.
¿Siempre es posible escribir una forma no recursiva para cada función recursiva?
Sí. Una prueba formal simple es demostrar que tanto la recursividad µ como un cálculo no recursivo como GOTO son 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í hay una:
Un programa GOTO es una secuencia de comandos P ejecutados en una máquina de registro tal que P es uno de los siguientes:
HALT, que detiene la ejecuciónr = r + 1¿Dónderestá algún registro?r = r – 1¿Dónderestá algún registro?GOTO xdondexhay una etiquetaIF r ≠ 0 GOTO x¿Dónderestá cualquier registro yxes 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 obtener más información, consulte esta respuesta .
