algorithm - una - recursividad informatica




¿Qué es la recursión de cola? (16)

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:

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

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.

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


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 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 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.


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.


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 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.


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).


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.







tail-recursion