algorithm - saber - ¿Qué es la recursión de cola?

recursividad en programacion (23)

Mientras empecé a aprender lisp, me encontré con el término recursivo de cola . ¿Qué significa exactamente?

Una recursión de cola es una función recursiva en la que la función se llama a sí misma al final ("cola") de la función en la que no se realiza ningún cálculo después de la devolución de la llamada recursiva. Muchos compiladores se optimizan para cambiar una llamada recursiva a una cola recursiva o una llamada iterativa.

Consideremos el problema de computación factorial de un número.

Un enfoque directo sería:

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

Supongamos que llamas factorial (4). El árbol de recursión sería:

factorial(4) / / 4 factorial(3) / / 3 factorial(2) / / 2 factorial(1) / / 1 factorial(0) / 1

La profundidad máxima de recursión en el caso anterior es O (n).

Sin embargo, considere el siguiente ejemplo:

factAux(m,n): if n==0 then m; else factAux(m*n,n-1); factTail(n): return factAux(1,n);

El árbol de recursión para factTail (4) sería:

Aquí también, la profundidad máxima de recursión es O (n) pero ninguna de las llamadas agrega ninguna variable adicional a la pila. Por lo tanto, el compilador puede acabar con una pila.

Aquí hay un ejemplo de Common Lisp que hace factoriales usando la recursión de cola. Debido a la naturaleza sin apilamiento, uno podría realizar cálculos factoriales increíblemente grandes ...

(defun ! (n &optional (product 1)) (if (zerop n) product (! (1- n) (* product n))))

Y luego, por diversión, puedes probar (format nil "~R" (! 25))

Aquí hay un fragmento de código rápido que compara dos funciones. El primero es la recursión tradicional para encontrar el factorial de un número dado. El segundo utiliza la recursión de la cola.

Muy simple e intuitivo de entender.

Una forma sencilla de saber si una función recursiva es cola recursiva, es si devuelve un valor concreto en el caso base. Lo que significa que no devuelve 1 o verdadero ni nada de eso. Es más probable que devuelva alguna variante de uno de los parámetros del método.

Otra forma de saberlo es si la llamada recursiva está libre de cualquier adición, aritmética, modificación, etc., lo que significa que no es más que una llamada recursiva pura.

public static int factorial(int mynumber) { if (mynumber == 1) { return 1; } else { return mynumber * factorial(--mynumber); } } public static int tail_factorial(int mynumber, int sofar) { if (mynumber == 1) { return sofar; } else { return tail_factorial(--mynumber, sofar * mynumber); } }

Aquí hay una versión de Perl 5 de la función tailrecsum mencionada anteriormente.

sub tail_rec_sum($;$){ my( $x,$running_total ) = (@_,0); return $running_total unless $x; @_ = ($x-1,$running_total+$x); goto &tail_rec_sum; # throw away current stack frame }

El archivo de jerga tiene esto que decir acerca de la definición de recursión de la cola:

recursión de la cola /n./

Si no estás harto de eso ya, mira la recursión de la cola.

En la recursión tradicional , el modelo típico es que primero realice sus llamadas recursivas, y luego tome el valor de retorno de la llamada recursiva y calcule el resultado. De esta manera, no obtendrá el resultado de su cálculo hasta que haya regresado de cada llamada recursiva.

En la recursión de cola , primero realiza sus cálculos y luego ejecuta la llamada recursiva, pasando los resultados de su paso actual al siguiente paso recursivo. Esto hace que la última declaración tenga la forma de (return (recursive-function params)) . Básicamente, el valor de retorno de cualquier paso recursivo dado es el mismo que el valor de retorno de la siguiente llamada recursiva .

La consecuencia de esto es que una vez que esté listo para realizar su próximo paso recursivo, ya no necesita el marco de pila actual. Esto permite una cierta optimización. De hecho, con un compilador escrito apropiadamente, nunca debe tener una sonrisa de desbordamiento de pila con una llamada recursiva de cola. Simplemente reutilice el marco de pila actual para el siguiente paso recursivo. Estoy bastante seguro de que Lisp hace esto.

En Java, aquí hay una posible implementación recursiva de la cola de la función de Fibonacci:

public int tailRecursive(final int n) { if (n <= 2) return 1; return tailRecursiveAux(n, 1, 1); } private int tailRecursiveAux(int n, int iter, int acc) { if (iter == n) return acc; return tailRecursiveAux(n, ++iter, acc + iter); }

Contraste esto con la implementación recursiva estándar:

public int recursive(final int n) { if (n <= 2) return 1; return recursive(n - 1) + recursive(n - 2); }

En lugar de explicarlo con palabras, aquí hay un ejemplo. Esta es una versión de esquema de la función factorial:

(define (factorial x) (if (= x 0) 1 (* x (factorial (- x 1)))))

Aquí hay una versión de factorial que es recursiva de cola:

(define factorial (letrec ((fact (lambda (x accum) (if (= x 0) accum (fact (- x 1) (* accum x)))))) (lambda (x) (fact x 1))))

Notará que en la primera versión la llamada recursiva a los hechos se envía a la expresión de multiplicación y, por lo tanto, el estado debe guardarse en la pila al realizar la llamada recursiva. En la versión recursiva de cola no hay otra expresión S que espere el valor de la llamada recursiva, y como no hay trabajo adicional por hacer, el estado no tiene que guardarse en la pila. Como regla general, las funciones recursivas de cola de Scheme utilizan un espacio de pila constante.

En resumen, una recursión de cola tiene la llamada recursiva como la última instrucción en la función para que no tenga que esperar la llamada recursiva.

Así que esta es una recursión de cola, es decir, N (x - 1, p * x) es la última declaración en la función en la que el compilador es inteligente para darse cuenta de que se puede optimizar a un bucle for (factorial). El segundo parámetro p lleva el valor del producto intermedio.

function N(x, p) { return x == 1 ? p : N(x - 1, p * x); }

Esta es la forma no recursiva de cola de escribir la función factorial anterior (aunque algunos compiladores de C ++ pueden ser capaces de optimizarla de todos modos).

function N(x) { return x == 1 ? 1 : x * N(x - 1); }

pero esto no es

function F(x) { if (x == 1) return 0; if (x == 2) return 1; return F(x - 1) + F(x - 2); }

Escribí un post largo titulado " Comprendiendo la recursión de cola - Visual Studio C ++ - Vista de ensamblaje "

Esta pregunta tiene muchas respuestas geniales ... pero no puedo evitar agregar una opinión alternativa sobre cómo definir la "recursión de la cola", o al menos la "recursión de la cola adecuada". A saber: ¿debería uno verlo como una propiedad de una expresión particular en un programa? ¿O debería uno verlo como una propiedad de una implementación de un lenguaje de programación ?

Para más información sobre este último punto de vista, hay un paper clásico de Will Clinger, "Correcta recursión de la cola y eficiencia del espacio" (PLDI 1998), que definió la "recursión de la cola apropiada" como una propiedad de una implementación de lenguaje de programación. La definición se construye para permitir que uno ignore los detalles de la implementación (por ejemplo, si la pila de llamadas se representa realmente a través de la pila en tiempo de ejecución o a través de una lista de marcos vinculados asignados al montón).

Para lograr esto, utiliza un análisis asintótico: no del tiempo de ejecución del programa como se suele ver, sino del uso del espacio del programa. De esta manera, el uso del espacio de una lista vinculada asignada a un montón frente a una pila de llamadas en tiempo de ejecución termina siendo asintóticamente equivalente; así que uno puede ignorar ese detalle de implementación de lenguaje de programación (un detalle que ciertamente importa un poco en la práctica, pero puede enturbiar las aguas cuando intenta determinar si una implementación determinada cumple con el requisito de ser "cola de propiedad recursiva" )

El documento merece un estudio cuidadoso por varias razones:

Proporciona una definición inductiva de las expresiones de cola y las llamadas de cola de un programa. (Tal definición, y por qué tales llamadas son importantes, parece ser el tema de la mayoría de las otras respuestas que se dan aquí).
Aquí están esas definiciones, solo para proporcionar un sabor del texto:
Definición 1 Las expresiones de cola de un programa escrito en Core Scheme se definen inductivamente de la siguiente manera.
1. El cuerpo de una expresión lambda es una expresión de cola.
2. Si (if E0 E1 E2) es una expresión de cola, entonces E1 y E2 son expresiones de cola.
3. Nada más es una expresión de cola.
Definición 2 Una llamada de cola es una expresión de cola que es una llamada de procedimiento.

(una llamada recursiva de cola, o como dice el documento, "llamada de cola automática" es un caso especial de una llamada de cola en la que se invoca el procedimiento en sí).

Proporciona definiciones formales para seis "máquinas" diferentes para evaluar el esquema central, donde cada máquina tiene el mismo comportamiento observable, excepto la clase de complejidad de espacio asintótica en que se encuentra cada una.
Por ejemplo, después de dar definiciones para máquinas con, respectivamente, 1. administración de memoria basada en pila, 2. recolección de basura pero no llamadas de cola, 3. recolección de basura y llamadas de cola, el documento continúa con estrategias de administración de almacenamiento aún más avanzadas, como 4. "evlis tail recursion", donde el entorno no necesita ser preservado a través de la evaluación del último argumento de subexpresión en una llamada de cola, 5. reduciendo el ambiente de un cierre a solo las variables libres de ese cierre, y 6. La llamada semántica "segura para el espacio" definida por Appel y Shao .
Para probar que las máquinas realmente pertenecen a seis clases distintas de complejidad espacial, el papel, para cada par de máquinas en comparación, proporciona ejemplos concretos de programas que expondrán la explosión de espacio asintótica en una máquina pero no en la otra.

(Al leer mi respuesta ahora, no estoy seguro de haber logrado captar los puntos cruciales del paper . Pero, por desgracia, no puedo dedicar más tiempo a desarrollar esta respuesta en este momento).

Este es un extracto de la Estructura e Interpretación de Programas de Computación sobre la recursión de la cola.

Al contrastar iteración y recursión, debemos tener cuidado de no confundir la noción de un proceso recursivo con la noción de un procedimiento recursivo. Cuando describimos un procedimiento como recursivo, nos referimos al hecho sintáctico de que la definición del procedimiento se refiere (directa o indirectamente) al procedimiento en sí. Pero cuando describimos un proceso como siguiendo un patrón que es, digamos, linealmente recursivo, estamos hablando de cómo evoluciona el proceso, no de la sintaxis de cómo se escribe un procedimiento. Puede parecer inquietante que nos referimos a un procedimiento recursivo, como el iterativo de hechos, como un proceso iterativo. Sin embargo, el proceso realmente es iterativo: su estado es capturado completamente por sus tres variables de estado, y un intérprete necesita realizar un seguimiento de solo tres variables para ejecutar el proceso.
Una razón por la que la distinción entre proceso y procedimiento puede ser confusa es que la mayoría de las implementaciones de lenguajes comunes (incluidos Ada, Pascal y C) están diseñadas de tal manera que la interpretación de cualquier procedimiento recursivo consume una cantidad de memoria que crece con el Número de llamadas a procedimientos, incluso cuando el proceso descrito es, en principio, iterativo. Como consecuencia, estos lenguajes pueden describir procesos iterativos solo recurriendo a "construcciones en bucle" para propósitos especiales, tales como hacer, repetir, hasta, para y mientras. La implementación de Scheme no comparte este defecto. Ejecutará un proceso iterativo en un espacio constante, incluso si el proceso iterativo se describe mediante un procedimiento recursivo. Una implementación con esta propiedad se llama tail-recursive. Con una implementación recursiva de cola, la iteración se puede expresar utilizando el mecanismo de llamada de procedimiento ordinario, de modo que las construcciones de iteración especial son útiles solo como azúcar sintáctica.

Este extracto del libro Programación en Lua muestra cómo hacer una recursión de la cola adecuada (en Lua, pero también debería aplicarse a Lisp) y por qué es mejor.

Una llamada de cola [recursión de cola] es un tipo de goto vestido como una llamada. Una llamada de cola ocurre cuando una función llama a otra como su última acción, por lo que no tiene nada más que hacer. Por ejemplo, en el siguiente código, la llamada a g es una llamada de cola:
function f (x) return g(x) end
Después de que f llama a g , no tiene nada más que hacer. En tales situaciones, el programa no necesita volver a la función de llamada cuando finaliza la función llamada. Por lo tanto, después de la llamada de cola, el programa no necesita mantener ninguna información sobre la función de llamada en la pila. ...
Debido a que una llamada de cola correcta no usa espacio de pila, no hay límite en el número de llamadas de cola "anidadas" que un programa puede hacer. Por ejemplo, podemos llamar a la siguiente función con cualquier número como argumento; nunca desbordará la pila:
function foo (n) if n > 0 then return foo(n - 1) end end
... Como dije antes, una llamada de cola es una especie de goto. Como tal, una aplicación bastante útil de llamadas de cola adecuadas en Lua es para la programación de máquinas de estado. Tales aplicaciones pueden representar cada estado por una función; cambiar de estado es ir a (o llamar) una función específica. Como ejemplo, consideremos un simple juego de laberinto. El laberinto tiene varias habitaciones, cada una con hasta cuatro puertas: norte, sur, este y oeste. En cada paso, el usuario ingresa una dirección de movimiento. Si hay una puerta en esa dirección, el usuario se dirige a la habitación correspondiente; De lo contrario, el programa imprime una advertencia. El objetivo es pasar de una habitación inicial a una habitación final.
Este juego es una máquina de estado típica, donde la sala actual es el estado. Podemos implementar dicho laberinto con una función para cada habitación. Usamos llamadas de cola para pasar de una habitación a otra. Un pequeño laberinto con cuatro habitaciones podría verse así:
function room1 () local move = io.read() if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end end function room2 () local move = io.read() if move == "south" then return room4() elseif move == "west" then return room1() else print("invalid move") return room2() end end function room3 () local move = io.read() if move == "north" then return room1() elseif move == "east" then return room4() else print("invalid move") return room3() end end function room4 () print("congratulations!") end

Así que ya ves, cuando haces una llamada recursiva como:

function x(n) if n==0 then return 0 n= n-2 return x(n) + 1 end

Esto no es recursivo porque todavía tiene cosas que hacer (agregar 1) en esa función después de que se realiza la llamada recursiva. Si ingresa un número muy alto, probablemente causará un desbordamiento de pila.

Esto significa que en lugar de tener que empujar el puntero de instrucción en la pila, simplemente puede saltar a la parte superior de una función recursiva y continuar la ejecución. Esto permite que las funciones se recuperen indefinidamente sin desbordar la pila.

Escribí una blog sobre el tema, que contiene ejemplos gráficos de cómo se ven los marcos de pila.

Hay dos tipos básicos de recursiones: recursión de la cabeza y recursión de la cola.

En la recursión principal , una función realiza su llamada recursiva y luego realiza algunos cálculos más, tal vez utilizando el resultado de la llamada recursiva, por ejemplo.
En una función recursiva de cola , todos los cálculos suceden primero y la llamada recursiva es lo último que sucede.

Tomado de this post super impresionante. Por favor considere leerlo.

La mejor manera de entender la tail call recursion es: un caso especial de recursión donde la última llamada (o la llamada de la cola) es la función en sí.

Comparando los ejemplos proporcionados en Python:

def recsum(x): if x == 1: return x else: return x + recsum(x - 1)

^ RECURSION

def tailrecsum(x, running_total=0): if x == 0: return running_total else: return tailrecsum(x - 1, running_total + x)

^ RECURSIÓN DE LA COLA

Como puede ver en la versión general recursiva, la llamada final en el bloque de código es x + recsum(x - 1) . Entonces, después de llamar al método de recsum , hay otra operación que es x + ..

Sin embargo, en la versión recursiva de cola, la llamada final (o la llamada de cola) en el bloque de código es tailrecsum(x - 1, running_total + x) que significa que la última llamada se realiza al método en sí y no se realiza ninguna operación después de eso.

Este punto es importante porque la recursión de la cola como se ve aquí no hace crecer la memoria porque cuando la máquina virtual subyacente ve una función que se llama a sí misma en una posición de cola (la última expresión que se evalúa en una función), elimina el marco de pila actual, que es conocido como Tail Call Optimization (TCO).

EDITAR

NÓTESE BIEN. Tenga en cuenta que el ejemplo anterior está escrito en Python cuyo tiempo de ejecución no es compatible con TCO. Esto es solo un ejemplo para explicar el punto. TCO es compatible con idiomas como Scheme, Haskell, etc.

La recursión de cola es la vida que estás viviendo en este momento. Constantemente recicla el mismo marco de pila, una y otra vez, porque no hay ninguna razón o medio para volver a un marco "anterior". El pasado ha terminado y hecho para que pueda ser descartado. Obtienes un cuadro, moviéndote para siempre hacia el futuro, hasta que tu proceso muera inevitablemente.

_{La analogía se rompe cuando consideras que algunos procesos pueden utilizar marcos adicionales, pero aún se consideran recursivos de cola si la pila no crece infinitamente.}

La recursión de cola se refiere a la última llamada recursiva en la última instrucción lógica en el algoritmo recursivo.

Normalmente, en la recursión tiene un caso base que es lo que detiene las llamadas recursivas y comienza a hacer estallar la pila de llamadas. Para usar un ejemplo clásico, aunque más C-ish que Lisp, la función factorial ilustra la recursión de la cola. La llamada recursiva ocurre después de verificar la condición del caso base.

factorial(x, fac) { if (x == 1) return fac; else return factorial(x-1, x*fac); }

Tenga en cuenta que la llamada inicial a factorial debe ser factorial (n, 1), donde n es el número para el cual se debe calcular el factorial.

No soy un programador de Lisp, pero creo que this ayudará.

Básicamente es un estilo de programación tal que la llamada recursiva es lo último que haces.

Para comprender algunas de las diferencias principales entre la recursión de la llamada de cola y la no recurrente de la llamada de cola, podemos explorar las implementaciones .NET de estas técnicas.

Aquí hay un artículo con algunos ejemplos en C #, F # y C ++ / CLI: Aventuras en recursión de cola en C #, F # y C ++ / CLI .

C # no se optimiza para la recursión de la llamada de cola, mientras que F # lo hace.

Las diferencias de principio involucran bucles vs. cálculo Lambda. C # está diseñado teniendo en cuenta los bucles, mientras que F # se construye a partir de los principios del cálculo Lambda. Para un libro muy bueno (y gratuito) sobre los principios del cálculo Lambda, vea: Estructura e interpretación de programas de computadora, por Abelson, Sussman y Sussman .

Con respecto a las llamadas de cola en F #, para un artículo introductorio muy bueno, vea: Introducción detallada a las llamadas de cola en F # . Finalmente, aquí hay un artículo que cubre la diferencia entre la recursión sin cola y la recursión de la llamada de cola (en F #): Recursión de cola frente a recursión sin cola en F sharp .

Si desea leer sobre algunas de las diferencias de diseño de la recursión de la llamada de cola entre C # y F #, consulte: Generación de código de operación de llamada de cola en C # y F # .

Si le interesa lo suficiente como para saber qué condiciones impiden que el compilador de C # realice optimizaciones de llamada de cola, consulte este artículo: Condiciones de llamada de cola de JIT CLR .

Recursión significa una función que se llama a sí misma. Por ejemplo:

(define (un-ended name) (un-ended ''me) (print "How can I get here?"))

Recursión de cola significa la recursión que concluye la función:

(define (un-ended name) (print "hello") (un-ended ''me))

Ver, lo último que hace la función sin terminar (procedimiento, en la jerga de Scheme) es llamarse a sí mismo. Otro ejemplo (más útil) es:

(define (map lst op) (define (helper done left) (if (nil? left) done (helper (cons (op (car left)) done) (cdr left)))) (reverse (helper ''() lst)))

En el procedimiento de ayuda, lo ÚLTIMO que hace si se deja no es nulo es llamarse a sí mismo (DESPUÉS de algo y cdr algo). Esto es básicamente cómo se asigna una lista.

La recursión de cola tiene una gran ventaja de que el intérprete (o compilador, que depende del idioma y el proveedor) puede optimizarla y transformarla en algo equivalente a un bucle while. De hecho, en la tradición de Scheme, la mayoría de los bucles "for" y "while" se realizan en forma de recursión de cola (no hay ningún tiempo para, mientras que yo sepa).

Un punto importante es que la recursión de la cola es esencialmente equivalente al bucle. No es solo una cuestión de optimización del compilador, sino un hecho fundamental sobre la expresividad. Esto va en ambos sentidos: puede tomar cualquier bucle de la forma

while(E) { S }; return Q

donde E y Q son expresiones y S es una secuencia de sentencias, y la convierte en una función recursiva de cola

f() = if E then { S; return f() } else { return Q }

Por supuesto, E , S y Q deben definirse para calcular algún valor interesante sobre algunas variables. Por ejemplo, la función de bucle.

sum(n) { int i = 1, k = 0; while( i <= n ) { k += i; ++i; } return k; }

es equivalente a la (s) función (es) recursiva (s) de la cola

sum_aux(n,i,k) { if( i <= n ) { return sum_aux(n,i+1,k+i); } else { return k; } } sum(n) { return sum_aux(n,1,0); }

(Este "ajuste" de la función recursiva de la cola con una función con menos parámetros es un lenguaje funcional común).

Usando la recursión regular, cada llamada recursiva inserta otra entrada en la pila de llamadas. Cuando se completa la recursión, la aplicación debe quitar cada entrada por completo hacia abajo.

Con la recursión de cola, dependiendo del idioma, el compilador puede colapsar la pila en una sola entrada, para que ahorre espacio en la pila ... Una consulta recursiva grande puede provocar un desbordamiento de pila.

Básicamente, las recursiones de cola se pueden optimizar en iteración.

Considere una función simple que agrega los primeros N enteros. (por ejemplo, sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ).

Aquí hay una implementación simple de JavaScript que usa recursión:

function recsum(x) { if (x===1) { return x; } else { return x + recsum(x-1); } }

Si llamó a recsum(5) , esto es lo que evaluaría el intérprete de JavaScript:

recsum(5) 5 + recsum(4) 5 + (4 + recsum(3)) 5 + (4 + (3 + recsum(2))) 5 + (4 + (3 + (2 + recsum(1)))) 5 + (4 + (3 + (2 + 1))) 15

Observe cómo cada llamada recursiva debe completarse antes de que el intérprete de JavaScript comience a realizar el trabajo de cálculo de la suma.

Aquí hay una versión recursiva de la cola de la misma función:

function tailrecsum(x, running_total=0) { if (x===0) { return running_total; } else { return tailrecsum(x-1, running_total+x); } }

Aquí está la secuencia de eventos que ocurrirían si llamara tailrecsum(5) , (que en realidad sería tailrecsum(5, 0) , debido al segundo argumento predeterminado).

tailrecsum(5, 0) tailrecsum(4, 5) tailrecsum(3, 9) tailrecsum(2, 12) tailrecsum(1, 14) tailrecsum(0, 15) 15

En el caso de la cola recursiva, con cada evaluación de la llamada recursiva, se actualiza el running_total .

Nota: La respuesta original usó ejemplos de Python. Estos se han cambiado a JavaScript, ya que los intérpretes modernos de JavaScript admiten la optimización de llamadas de cola, pero los intérpretes de Python no.