¿Cómo funciona exactamente la recursividad de cola?

121

Casi entiendo cómo funciona la recursividad de cola y la diferencia entre ella y una recursividad normal. Yo solamente no entiendo por qué no se requiere pila de recordar su dirección de retorno.

// tail recursion
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

int factorial (int n) {
    return fac_times (n, 1);
}

// normal recursion
int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

No hay nada que hacer después de llamar a una función en sí misma en una función de recursión de cola, pero no tiene sentido para mí.

Alan Coromano
fuente
16
La recursión de la cola es una recursión "normal". Solo significa que la recursión ocurre al final de la función.
Pete Becker
77
... Pero se puede implementar de una manera diferente a nivel de IL que la recursividad normal, reduciendo la profundidad de la pila.
KeithS
2
Por cierto, gcc puede realizar la eliminación de recursión de cola en el ejemplo "normal" aquí.
dmckee --- ex-gatito moderador
1
@ Geek: soy un desarrollador de C #, por lo que mi "lenguaje ensamblador" es MSIL o simplemente IL. Para C / C ++, reemplace IL con ASM.
KeithS
1
@ShannonSeverance Descubrí que gcc lo está haciendo por el simple expediente que examina el código de ensamblaje emitido con sin -O3. El enlace es para una discusión anterior que cubre un terreno muy similar y discute lo que es necesario para implementar esta optimización.
dmckee --- ex-gatito moderador

Respuestas:

169

El compilador simplemente puede transformar esto

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

en algo como esto:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}
Alexey Frunze
fuente
2
@ Mr.32 No entiendo tu pregunta. Convertí la función en una equivalente pero sin recursión explícita (es decir, sin llamadas a funciones explícitas). Si cambia la lógica a algo no equivalente, de hecho puede hacer que la función se repita para siempre en algunos o en todos los casos.
Alexey Frunze
18
Entonces, ¿la recursividad de colas es efectiva solo porque el compilador la optimiza? ¿Y de lo contrario sería lo mismo que una recursión normal en términos de memoria de pila?
Alan Coromano
34
Sí. Si el compilador no puede reducir la recursividad a un bucle, está atascado con la recursividad. Todo o nada.
Alexey Frunze
3
@AlanDert: correcto. También puede considerar que la recursión de cola es un caso especial de la "optimización de llamada de cola", especial porque la llamada de cola tiene la misma función. En general, cualquier llamada de cola (con los mismos requisitos en "no queda trabajo por hacer" como se aplica a la recursión de cola, y donde el valor de retorno de la llamada de cola se devuelve directamente) puede optimizarse si el compilador puede hacer la llamada en un forma que configura la dirección de retorno de la función llamada como la dirección de retorno de la función que realiza la llamada de cola, en lugar de la dirección desde la que se realizó la llamada de cola.
Steve Jessop
1
@AlanDert en C esta es solo una optimización que ningún estándar impone, por lo que el código portátil no debería depender de ella. Pero hay idiomas (Scheme es un ejemplo), donde el estándar impone la optimización de la recursividad de la cola, por lo que no debe preocuparse de que se acumule el desbordamiento en algunos entornos.
Jan Wrobel
57

Usted pregunta por qué "no requiere pila para recordar su dirección de retorno".

Me gustaría cambiar esto. Se hace uso de la pila de recordar la dirección de retorno. El truco es que la función en la que ocurre la recursión de cola tiene su propia dirección de retorno en la pila, y cuando salta a la función llamada, tratará esto como su propia dirección de retorno.

Concretamente, sin optimización de llamada de cola:

f: ...
   CALL g
   RET
g:
   ...
   RET

En este caso, cuando gse llama, la pila se verá así:

   SP ->  Return address of "g"
          Return address of "f"

Por otro lado, con la optimización de llamada de cola:

f: ...
   JUMP g
g:
   ...
   RET

En este caso, cuando gse llama, la pila se verá así:

   SP ->  Return address of "f"

Claramente, cuando gregrese, volverá a la ubicación desde donde fse llamó.

EDITAR : El ejemplo anterior usa el caso donde una función llama a otra función. El mecanismo es idéntico cuando la función se llama a sí misma.

Lindydancer
fuente
8
Esta es una respuesta mucho mejor que las otras respuestas. Lo más probable es que el compilador no tenga algún caso mágico especial para convertir código recursivo de cola. Simplemente realiza una optimización normal de la última llamada que sucede que va a la misma función.
Arte
12

El compilador puede transformar la recursividad de la cola en un bucle, especialmente cuando se usan acumuladores.

// tail recursion
int fac_times (int n, int acc = 1) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

compilaría algo como

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}
mepcotterell
fuente
3
No es tan inteligente como la implementación de Alexey ... y sí, eso es un cumplido.
Matthieu M.
1
En realidad, el resultado parece más simple, pero creo que el código para implementar esta transformación sería MUCHO más "inteligente" que la etiqueta / goto o simplemente la eliminación de llamadas de cola (ver la respuesta de Lindydancer).
Phob
Si esto es todo, ¿por qué la gente se entusiasma tanto? No veo a nadie emocionado por los bucles.
Buh Buh
@BuhBuh: esto no tiene stackoverflow, y evita la inserción / extracción de parámetros de la pila. Para un circuito cerrado como este, puede hacer una gran diferencia. Aparte de eso, la gente no debería estar emocionada.
Mooing Duck
11

Hay dos elementos que deben estar presentes en una función recursiva:

  1. La llamada recursiva
  2. Un lugar para mantener el recuento de los valores de retorno.

Una función recursiva "regular" mantiene (2) en el marco de la pila.

Los valores de retorno en la función recursiva regular se componen de dos tipos de valores:

  • Otros valores de retorno
  • Resultado del cálculo de la función propia

Veamos tu ejemplo:

int factorial (int n) {
    if (n == 0) return 1;
    else return n * factorial(n - 1);
}

El cuadro f (5) "almacena" el resultado de su propio cálculo (5) y el valor de f (4), por ejemplo. Si llamo factorial (5), justo antes de que las llamadas de la pila comiencen a colapsar, tengo:

 [Stack_f(5): return 5 * [Stack_f(4): 4 * [Stack_f(3): 3 * ... [1[1]]

Observe que cada pila almacena, además de los valores que mencioné, todo el alcance de la función. Entonces, el uso de memoria para una función recursiva f es O (x), donde x es el número de llamadas recursivas que tengo que hacer. Entonces, si necesito 1kb de RAM para calcular factorial (1) o factorial (2), necesito ~ 100k para calcular factorial (100), y así sucesivamente.

Una función recursiva de cola puso (2) en sus argumentos.

En una Recursión de cola, paso el resultado de los cálculos parciales en cada cuadro recursivo al siguiente usando parámetros. Veamos nuestro ejemplo factorial, Tail Recursive:

int factorial (int n) {int helper (int num, int acumulado) {if num == 0 return acumulado de lo contrario return helper (num - 1, acumulado * num)} return helper (n, 1)
}

Veamos sus marcos en factorial (4):

[Stack f(4, 5): Stack f(3, 20): [Stack f(2,60): [Stack f(1, 120): 120]]]]

¿Ves las diferencias? En las llamadas recursivas "regulares", las funciones de retorno componen recursivamente el valor final. En Tail Recursion solo hacen referencia al caso base (el último evaluado) . Llamamos acumulador al argumento que realiza un seguimiento de los valores más antiguos.

Plantillas de recursión

La función recursiva regular es la siguiente:

type regular(n)
    base_case
    computation
    return (result of computation) combined with (regular(n towards base case))

Para transformarlo en una recursión de cola, nosotros:

  • Introducir una función auxiliar que lleve el acumulador.
  • ejecute la función auxiliar dentro de la función principal, con el acumulador configurado en el caso base.

Mira:

type tail(n):
    type helper(n, accumulator):
        if n == base case
            return accumulator
        computation
        accumulator = computation combined with accumulator
        return helper(n towards base case, accumulator)
    helper(n, base case)

¿Ver la diferencia?

Tail Call optimization

Como no se está almacenando ningún estado en las pilas de Casos No Fronterizos de la Llamada de Cola, no son tan importantes. Algunos idiomas / intérpretes luego sustituyen la pila anterior por la nueva. Por lo tanto, sin marcos de pila que limiten el número de llamadas, las Llamadas de cola se comportan como un bucle for en estos casos.

Depende de su compilador optimizarlo o no.

Lucas Ribeiro
fuente
6

Aquí hay un ejemplo simple que muestra cómo funcionan las funciones recursivas:

long f (long n)
{

    if (n == 0) // have we reached the bottom of the ocean ?
        return 0;

    // code executed in the descendence

    return f(n-1) + 1; // recurrence

    // code executed in the ascendence

}

La recurrencia de cola es una función recursiva simple, donde la recurrencia se realiza al final de la función, por lo tanto, no se hace ningún código en ascendencia, lo que ayuda a la mayoría de los compiladores de lenguajes de programación de alto nivel a hacer lo que se conoce como Optimización de recursión de cola , también tiene optimización más compleja conocida como módulo de recursión de cola

Khaled.K
fuente
1

La función recursiva es una función que llama por sí misma

Permite a los programadores escribir programas eficientes utilizando una cantidad mínima de código .

La desventaja es que pueden causar bucles infinitos y otros resultados inesperados si no se escriben correctamente .

Explicaré la función recursiva simple y la función recursiva de cola

Para escribir una función recursiva simple

  1. El primer punto a considerar es cuándo debe decidir salir del bucle, que es el bucle if
  2. El segundo es qué proceso hacer si somos nuestra propia función.

Del ejemplo dado:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

Del ejemplo anterior

if(n <=1)
     return 1;

Es el factor decisivo cuando salir del ciclo

else 
     return n * fact(n-1);

¿Se debe realizar el procesamiento real?

Permítanme romper la tarea uno por uno para una fácil comprensión.

Veamos qué sucede internamente si corro fact(4)

  1. Sustituyendo n = 4
public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

Ifel bucle falla, por lo que pasa al elsebucle y regresa4 * fact(3)

  1. En la memoria de pila, tenemos 4 * fact(3)

    Sustituyendo n = 3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

Ifel bucle falla, por lo que pasa al elsebucle

entonces regresa 3 * fact(2)

Recuerde que llamamos `` `4 * fact (3)` `

La salida para fact(3) = 3 * fact(2)

Hasta ahora la pila tiene 4 * fact(3) = 4 * 3 * fact(2)

  1. En la memoria de pila, tenemos 4 * 3 * fact(2)

    Sustituyendo n = 2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

Ifel bucle falla, por lo que pasa al elsebucle

entonces regresa 2 * fact(1)

Recuerda que llamamos 4 * 3 * fact(2)

La salida para fact(2) = 2 * fact(1)

Hasta ahora la pila tiene 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

  1. En la memoria de pila, tenemos 4 * 3 * 2 * fact(1)

    Sustituyendo n = 1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If el bucle es verdadero

entonces regresa 1

Recuerda que llamamos 4 * 3 * 2 * fact(1)

La salida para fact(1) = 1

Hasta ahora la pila tiene 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

Finalmente, el resultado del hecho (4) = 4 * 3 * 2 * 1 = 24

ingrese la descripción de la imagen aquí

La recursión de la cola sería

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}
  1. Sustituyendo n = 4
public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

Ifel bucle falla, por lo que pasa al elsebucle y regresafact(3, 4)

  1. En la memoria de pila, tenemos fact(3, 4)

    Sustituyendo n = 3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

Ifel bucle falla, por lo que pasa al elsebucle

entonces regresa fact(2, 12)

  1. En la memoria de pila, tenemos fact(2, 12)

    Sustituyendo n = 2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

Ifel bucle falla, por lo que pasa al elsebucle

entonces regresa fact(1, 24)

  1. En la memoria de pila, tenemos fact(1, 24)

    Sustituyendo n = 1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If el bucle es verdadero

entonces regresa running_total

La salida para running_total = 24

Finalmente, el resultado del hecho (4,1) = 24

ingrese la descripción de la imagen aquí

Nursnaaz
fuente
0

Mi respuesta es más una conjetura, porque la recursividad es algo relacionado con la implementación interna.

En la recursividad de cola, la función recursiva se llama al final de la misma función. Probablemente el compilador puede optimizar de la siguiente manera:

  1. Deje que la función en curso termine (es decir, se recupera la pila usada)
  2. Almacene las variables que se utilizarán como argumentos para la función en un almacenamiento temporal
  3. Después de esto, vuelva a llamar a la función con el argumento almacenado temporalmente

Como puede ver, estamos terminando la función original antes de la próxima iteración de la misma función, por lo que en realidad no estamos "usando" la pila.

Pero creo que si hay destructores a los que se debe llamar dentro de la función, entonces esta optimización puede no aplicarse.

iammilind
fuente
0

El compilador es lo suficientemente inteligente como para comprender la recursividad de cola. En el caso de que, al regresar de una llamada recursiva, no haya una operación pendiente y la última llamada sea recursiva, pertenece a la categoría de recursividad de cola. El compilador básicamente realiza la optimización de recursión de cola, eliminando la implementación de la pila. Considere debajo del código.

void tail(int i) {
    if(i<=0) return;
    else {
     system.out.print(i+"");
     tail(i-1);
    }
   }

Después de realizar la optimización, el código anterior se convierte en uno inferior.

void tail(int i) {
    blockToJump:{
    if(i<=0) return;
    else {
     system.out.print(i+"");
     i=i-1;
     continue blockToJump;  //jump to the bolckToJump
    }
    }
   }

Así es como el compilador optimiza la recursividad de cola.

Varunnuevothoughts
fuente