functional-programming - ejemplos - recursividad informatica

¿Hay problemas que no se pueden escribir usando la recursividad de cola?

Question

La recurrencia de la cola es una estrategia importante de optimización del rendimiento en los lenguajes funcionales, ya que permite que las llamadas recursivas consuman una pila constante (en lugar de O (n)).

¿Hay algún problema que simplemente no se puede escribir en un estilo recursivo de cola, o siempre es posible convertir una función ingenuamente recursiva en una recursiva de cola?

Si es así, ¿algún día los compiladores e intérpretes funcionales serán lo suficientemente inteligentes como para realizar la conversión automáticamente?

Answer 1

Cualquier algoritmo recursivo se puede reescribir como un algoritmo iterativo (tal vez requiera una pila o lista) y los algoritmos iterativos siempre se pueden reescribir como algoritmos recursivos de cola, así que creo que es cierto que cualquier solución recursiva se puede convertir de alguna manera en una solución recursiva .

(En los comentarios, Pascal Cuoq señala que cualquier algoritmo se puede convertir a un estilo de continuación de paso ).

Tenga en cuenta que el hecho de que algo sea recursivo de cola no significa que su uso de memoria sea constante. Simplemente significa que la pila de devolución de llamadas no crece.

Answer 2

Es cierto pero no útil observar que cualquier colección de funciones mutuamente recursivas se puede convertir en una función recursiva de cola. Esta observación está a la par del antiguo castaño de la década de 1960 que las construcciones de flujo de control podrían eliminarse porque cada programa podría escribirse como un bucle con una declaración de caso anidada en su interior.

Lo que es útil saber es que muchas funciones que obviamente no son recursivas de cola pueden convertirse a la forma recursiva de la cola mediante la adición de parámetros de acumulación . (Una versión extrema de esta transformación es la transformación al estilo de continuación de paso (CPS), pero la mayoría de los programadores encuentran que la salida de la transformación de CPS es difícil de leer).

Aquí hay un ejemplo de una función que es "recursiva" (en realidad solo itera) pero no recursiva de cola:

factorial n = if n == 0 then 1 else n * factorial (n-1)

En este caso, la multiplicación ocurre después de la llamada recursiva. Podemos crear una versión que sea recursiva de cola colocando el producto en un parámetro de acumulación:

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

La función interna f es recursiva de cola y se compila en un ciclo cerrado.

Encuentro las siguientes distinciones útiles:

• En un programa iterativo o recursivo, resuelve un problema de tamaño n resolviendo primero un subproblema de tamaño n-1 . La computación de la función factorial cae dentro de esta categoría, y puede realizarse de forma iterativa o recursiva. (Esta idea se generaliza, por ejemplo, a la función de Fibonacci, donde necesita tanto n-1 como n-2 para resolver n ).

• En un programa recursivo, resuelve un problema de tamaño n resolviendo primero dos subproblemas de tamaño n/2 . O, de forma más general, resuelve un problema de tamaño n resolviendo primero un subproblema de tamaño k uno de tamaño nk , donde 1 < k < n . Quicksort y mergesort son dos ejemplos de este tipo de problema, que se pueden programar fácilmente de forma recursiva, pero no es tan fácil programar de forma iterativa o utilizar solo la repetición de cola. (En esencia, tiene que simular la recursión utilizando una pila explícita).

• En la programación dinámica, resuelve un problema de tamaño n resolviendo primero todos los subproblemas de todos los tamaños k , donde k<n . Encontrar la ruta más corta de un punto a otro en el metro de Londres es un ejemplo de este tipo de problema. (El Metro de Londres es un gráfico con múltiples conexiones, y tú resuelves el problema encontrando primero todos los puntos para los que la ruta más corta es 1 parada, luego para la que la ruta más corta es 2 paradas, etc., etc.)

Solo el primer tipo de programa tiene una transformación simple en forma recursiva de cola.

Answer 3

No creo que algo como tak pueda implementar usando solo llamadas de cola. (no permite las continuación)

Answer 4

No puede hacer todo en O (1) espacio (teorema de jerarquía espacial). Si insiste en usar recursividad de cola, entonces puede almacenar la pila de llamadas como uno de los argumentos. Obviamente esto no cambia nada; en algún lugar internamente, hay una pila de llamadas, simplemente lo estás haciendo explícitamente visible.

Si es así, ¿algún día los compiladores e intérpretes funcionales serán lo suficientemente inteligentes como para realizar la conversión automáticamente?

Tal conversión no disminuirá la complejidad del espacio.

Como comentó Pascal Cuoq, otra forma es usar CPS ; todas las llamadas son recursivas de cola entonces.

Answer 5

Sí, en realidad puede tomar algún código y convertir todas las llamadas de función, y cada devolución, en una llamada final. Con lo que terminas se llama estilo de continuación de paso o CPS.

Por ejemplo, aquí hay una función que contiene dos llamadas recursivas:

(define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

Y así es como se vería si convirtieras esta función a un estilo de continuación de paso:

(define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

El argumento adicional, ctn , es un procedimiento que count-tree-cps tail-calls en lugar de devolver . (La respuesta de sdcvvc dice que no se puede hacer todo en O (1) espacio, y eso es correcto, aquí cada continuación es un cierre que ocupa algo de memoria).

No transformé las llamadas a car o cdr o + en llamadas de cola. Eso podría hacerse también, pero supongo que esas llamadas de hoja en realidad estarían en línea.

Ahora viene la parte divertida. Chicken Scheme realmente hace esta conversión en todo el código que compila. Los procedimientos compilados por Chicken nunca regresan . Hay un artículo clásico que explica por qué Chicken Scheme hace esto, escrito en 1994 antes de que se implementara Chicken: CONS no debería contradecir sus argumentos, Parte II: Cheney en la MTA

Sorprendentemente, el estilo de continuación de paso es bastante común en JavaScript. Puede usarlo para realizar cálculos de larga ejecución , evitando el mensaje emergente "script lento" del navegador. Y es atractivo para API asincrónicas. jQuery.get (un contenedor simple alrededor de XMLHttpRequest) está claramente en el estilo de continuación de paso; el último argumento es una función.