¿Cómo funciona exactamente la recursión de cola?

Casi entiendo cómo funciona la recursión de cola y la diferencia entre esta y una recursión normal. I solamente no entiendo porque no Requiere pila para 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 una función de recursión de cola, pero no tiene sentido para mí.

El compilador es simplemente capaz de transformar este

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;
}

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

Me gustaría darle la vuelta a esto. Eso lo hace use la pila para recordar la dirección de retorno. El truco es que la función en la que se produce la recursión final tiene su propia dirección de retorno en la pila, y cuando salta a la función llamada, la tratará 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 g se llama, la pila se verá así:

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

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

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

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

   SP ->  Return address of "f"

Claramente, cuando g regresa, regresará a la ubicación donde f fue llamado de.

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.

El compilador generalmente puede transformar la recursión de 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);
}

se compilaría a algo como

// accumulator
int fac_times (int n) {
    int acc = 1;
    while (n > 0) {
        acc *= n;
        n -= 1;
    }
    return acc;
}

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

1. La llamada recursiva
2. Un lugar para llevar la cuenta de los valores devueltos.

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

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

• Otros valores devueltos
• 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 marco f(5) “almacena” el resultado de su propio cálculo (5) y el valor de f(4), por ejemplo. Si llamo a 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]]

Tenga en cuenta 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 cola recursiva puso (2) en sus argumentos.

En una Tail Recursion, 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 accumulated)
        {
            if num == 0 return accumulated
            else return helper(num - 1, accumulated*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 “normales”, las funciones de retorno componen recursivamente el valor final. En Tail Recursion solo hacen referencia al caso base (último evaluado). Llamamos acumulador el argumento que realiza un seguimiento de los valores más antiguos.

Plantillas de recursividad

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 recursividad Tail hacemos:

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

Mirar:

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?

Optimización de llamadas de cola

Dado que no se almacena ningún estado en los casos no fronterizos de las pilas de Tail Call, no son tan importantes. Algunos idiomas/intérpretes sustituyen la pila anterior por la nueva. Entonces, sin marcos de pila que restrinjan la cantidad de llamadas, las Tail Calls se comportan como un bucle for en estos casos.

Depende de su compilador optimizarlo, o no.

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 recursión de cola es una función recursiva simple, donde la recurrencia se realiza al final de la función, por lo que no se realiza ningún código en ascenso, 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 recurrencia de colatambién tiene una optimización más compleja conocida como la Módulo de recursión de cola

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

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

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

voy a explicar los dos Función recursiva simple y función recursiva de cola

Para escribir un Función recursiva simple

1. El primer punto a considerar es cuándo debe decidir salir del bucle, que es el bucle if.
2. La segunda 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 va a realizar el procesamiento real?

Permítanme dividir la tarea una por una para facilitar la comprensión.

Veamos qué pasa 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);
}

If bucle falla por lo que va a else bucle para que regrese 4 * fact(3)

2. 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);
}

If bucle falla por lo que va a else lazo

por lo que vuelve 3 * fact(2)

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

3. 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);
}

If bucle falla por lo que va a else lazo

por lo que vuelve 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)

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

por lo que vuelve 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 de hecho(4) = 4 * 3 * 2 * 1 = 24

los Recursión de 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);
    }
}

If bucle falla por lo que va a else bucle para que regrese fact(3, 4)

2. 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);
    }
}

If bucle falla por lo que va a else lazo

por lo que vuelve fact(2, 12)

2. 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);
    }
}

If bucle falla por lo que va a else lazo

por lo que vuelve fact(1, 24)

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

por lo que vuelve running_total

La salida para running_total = 24

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

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

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

1. Deje que la función en curso finalice (es decir, se recupera la pila usada)
2. Almacene las variables que se van a utilizar como argumentos de la función en un almacenamiento temporal
3. Después de esto, vuelve 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 para llamar dentro de la función, es posible que esta optimización no se aplique.