algorithm - recursive - tail recursion java

¿Qué es la optimización de llamadas de cola?

Question

Muy simple, ¿qué es la optimización de llamadas de cola? Más específicamente, ¿Alguien puede mostrar algunos fragmentos de código pequeños donde podría aplicarse y dónde no, con una explicación de por qué?

Answer 1

1. Deberíamos asegurarnos de que no haya declaraciones goto en la función en sí misma ... cuidado por la función call, siendo lo último en la función de llamada.

2. Las recursiones a gran escala pueden usar esto para optimizaciones, pero en pequeña escala, la sobrecarga de instrucciones para hacer que la función llame a una llamada final reduce el propósito real.

3. TCO podría causar una función de ejecución para siempre:

   void eternity()
   {
       eternity();
   }

Answer 2

El enfoque de función recursiva tiene un problema. Se acumula una pila de llamadas de tamaño O (n), lo que hace que nuestra memoria total cueste O (n). Esto lo hace vulnerable a un error de desbordamiento de pila, donde la pila de llamadas es demasiado grande y se queda sin espacio. Plan de optimización de costos de cola (TCO). Donde puede optimizar las funciones recursivas para evitar la acumulación de una pila de llamadas alta y por lo tanto ahorra el costo de la memoria.

Hay muchos lenguajes que hacen TCO como (Javascript, Ruby y pocos C) donde Python y Java no hacen TCO.

El lenguaje de JavaScript se ha confirmado utilizando :) http://2ality.com/2015/06/tail-call-optimization.html

Answer 3

En primer lugar, tenga en cuenta que no todos los idiomas lo admiten.

TCO se aplica a un caso especial de recursión. La esencia de esto es que si lo último que hace en una función es llamarse a sí mismo (por ejemplo, se llama a sí mismo desde la posición "cola"), el compilador puede optimizar esto para que actúe como una iteración en lugar de una recursión estándar.

Verá, normalmente durante la recursión, el tiempo de ejecución debe realizar un seguimiento de todas las llamadas recursivas, de modo que cuando se devuelve, se puede reanudar en la llamada anterior y así sucesivamente. (Intente escribir manualmente el resultado de una llamada recursiva para tener una idea visual de cómo funciona esto). El seguimiento de todas las llamadas ocupa espacio, lo que se vuelve significativo cuando la función se llama mucho a sí misma. Pero con TCO, solo puede decir "volver al principio, solo que esta vez cambiamos los valores de los parámetros a estos nuevos". Puede hacerlo porque nada después de la llamada recursiva se refiere a esos valores.

Answer 4

La optimización de llamada de cola es donde puede evitar asignar un nuevo marco de pila para una función porque la función de llamada simplemente devolverá el valor que obtiene de la función llamada. El uso más común es la recursión de cola, donde una función recursiva escrita para aprovechar la optimización de la llamada de cola puede usar un espacio de pila constante.

Scheme es uno de los pocos lenguajes de programación que garantizan en la especificación que cualquier implementación debe proporcionar esta optimización (JavaScript también lo hace, comenzando con ES6) , así que aquí hay dos ejemplos de la función factorial en Scheme:

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

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

La primera función no es recursiva de cola porque cuando se realiza la llamada recursiva, la función debe realizar un seguimiento de la multiplicación que debe hacer con el resultado después de que se devuelve la llamada. Como tal, la pila se ve como sigue:

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

En contraste, la traza de la pila para el factorial recursivo de la cola tiene el siguiente aspecto:

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

Como puede ver, solo necesitamos realizar un seguimiento de la misma cantidad de datos para cada llamada a la realidad, ya que simplemente estamos devolviendo el valor que hemos recibido hasta la cima. Esto significa que incluso si tuviera que llamar (hecho 1000000), solo necesito la misma cantidad de espacio que (hecho 3). Este no es el caso con el hecho no recursivo de cola, y como tales valores grandes pueden causar un desbordamiento de pila.

Answer 5

Mira aquí:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

Como usted probablemente sepa, las llamadas a funciones recursivas pueden causar estragos en una pila; Es fácil quedarse rápidamente sin espacio de pila. La optimización de llamadas de cola es una forma mediante la cual puede crear un algoritmo de estilo recursivo que usa un espacio de pila constante, por lo tanto, no crece y crece y usted obtiene errores de pila.

Answer 6

Probablemente la mejor descripción de alto nivel que he encontrado para llamadas de cola, llamadas de cola recursivas y optimización de llamadas de cola es la publicación del blog

"Qué diablos es: una llamada de cola"

por Dan Sugalski. En la optimización de llamadas cola escribe:

Considera, por un momento, esta simple función:

sub foo (int a) {
  a += 15;
  return bar(a);
}

Entonces, ¿qué puedes hacer tú, o mejor dicho, tu compilador de idiomas? Bueno, lo que puede hacer es convertir el código del formulario return somefunc(); en el pop stack frame; goto somefunc(); secuencia de bajo nivel pop stack frame; goto somefunc(); pop stack frame; goto somefunc(); . En nuestro ejemplo, eso significa que antes de llamar a bar , foo limpia solo y luego, en lugar de llamar a bar como subrutina, hacemos una operación de bajo nivel para goto al inicio de la bar . Foo ya se ha limpiado a sí mismo de la pila, de modo que cuando empieza el bar , parece que el que llamó foo realmente ha llamado el bar , y cuando el bar devuelve su valor, lo devuelve directamente al que llamó foo , en lugar de devolverlo a foo lo cual luego devolverlo a su llamador.

Y en la recursión de la cola:

La recursión de la cola ocurre si una función, como su última operación, devuelve el resultado de llamarse a sí misma . Es más fácil lidiar con la recursión de la cola porque, en lugar de tener que saltar al principio de alguna función aleatoria en algún lugar, solo debes volver al principio de ti mismo, lo cual es una cosa muy simple.

Para que esto:

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

se convierte tranquilamente en:

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

Lo que me gusta de esta descripción es lo breve y fácil que es comprenderlo para aquellos que provienen de un imperativo de lenguaje (C, C ++, Java).

Answer 7

TCO (Tail Call Optimization) es el proceso mediante el cual un compilador inteligente puede realizar una llamada a una función y no tener espacio de pila adicional. La única situación en la que esto sucede es si la última instrucción ejecutada en una función f es una llamada a una función g (Nota: g puede ser f ). La clave aquí es que f ya no necesita espacio en la pila, simplemente llama g y luego devuelve lo que g devolvería. En este caso, se puede hacer la optimización de que g simplemente se ejecuta y devuelve cualquier valor que tenga para lo que se llama f.

Esta optimización puede hacer que las llamadas recursivas tomen espacio de pila constante, en lugar de explotar.

Ejemplo: esta función factorial no es TCOptimizable:

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

Esta función hace cosas además de llamar a otra función en su declaración de retorno.

La siguiente función es TCOptimizable:

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

Esto se debe a que lo último que sucede en cualquiera de estas funciones es llamar a otra función.

Answer 8

Veamos un ejemplo simple: la función factorial implementada en C.

Comenzamos con la obvia definición recursiva.

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

Una función termina con una llamada de cola si la última operación antes de que la función regrese es otra llamada de función. Si esta llamada invoca la misma función, es recursiva de cola.

A pesar de que fac() parece recursivo a la cola a primera vista, no es lo que realmente sucede.

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

Es decir, la última operación es la multiplicación y no la función de llamada.

Sin embargo, es posible volver a escribir fac() para que sea recursivo de cola pasando el valor acumulado a lo largo de la cadena de llamadas como un argumento adicional y pasando solo el resultado final de nuevo como valor de retorno:

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

Ahora, ¿por qué es esto útil? Debido a que regresamos inmediatamente después de la llamada de cola, podemos descartar el cuadro de pila anterior antes de invocar la función en la posición de cola o, en caso de funciones recursivas, reutilizar el cuadro de pila como está.

La optimización de llamadas de cola transforma nuestro código recursivo en

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

Esto puede ser incorporado en fac() y llegamos a

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

que es equivalente a

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

Como podemos ver aquí, un optimizador lo suficientemente avanzado puede reemplazar la recursión de la cola con la iteración, que es mucho más eficiente, ya que evita la sobrecarga de llamadas a funciones y solo utiliza una cantidad constante de espacio de pila.