programacion - recursividad valor

¿Cómo funciona exactamente la recursividad de cola?

Question

Casi entiendo cómo funciona la recursividad de cola y la diferencia entre ella y una recursión normal. Solo que no entiendo por qué no requiere que la pila recuerde 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í.

Answer 1

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

1. La llamada recursiva
2. Un lugar para contar 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 propietaria

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 a 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 recursiva de cola pone (2) en sus argumentos.

En una recursividad de cola, paso el resultado de los cálculos parciales en cada trama recursiva a la siguiente utilizando los 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, acumulado * num)} return helper (n, 1)
}

Veamos sus cuadros en factorial (4):

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

¿Ves las diferencias? En 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 el argumento que hace un seguimiento de los valores anteriores.

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:

• Introduzca una función de ayuda que lleva el acumulador
• ejecute la función auxiliar dentro de la función principal, con el acumulador establecido en la caja 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?

Optimización de llamadas de cola

Como no se almacena ningún estado en los casos no fronterizos de las pilas de llamadas de cola, no son tan importantes. Algunos idiomas / intérpretes luego sustituyen la pila anterior por la nueva. Entonces, sin marcos de pila que limiten el número de llamadas, las Llamadas en cola se comportan como un bucle for en estos casos.

Depende de tu compilador optimizarlo o no.

Answer 2

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 recursividad 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 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 recursividad de cola. optimización más compleja conocida como módulo de recursión de cola

Answer 3

El compilador es lo suficientemente inteligente como para entender la recursividad final. En caso de que, al regresar de una llamada recursiva, no haya una operación pendiente y la llamada recursiva sea la última, caiga dentro de la categoría de recursividad final. El compilador básicamente realiza la optimización de la recursividad de la cola, eliminando la implementación de la pila. Considere el siguiente 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 realiza la Optimización de Recursión de Cola.

Answer 4

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

Answer 5

La recursividad de cola generalmente puede transformarse en un bucle por el compilador, 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 así como

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

Answer 6

Mi respuesta es más bien una suposición, 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 se acabe (es decir, se retire la pila usada)
2. Almacene las variables que se van a usar 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 para ser llamados dentro de la función, esta optimización puede no aplicarse.

Answer 7

Usted pregunta por qué "no requiere que la pila recuerde su dirección de retorno".

Me gustaría cambiar esto. Utiliza la pila para recordar la dirección de retorno. El truco es que la función en la que se produce 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 llamadas de cola:

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

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

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

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

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

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

   SP ->  Return address of "f"

Claramente, cuando g vuelve, volverá a la ubicación desde la que se invocó f .

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.