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

12 minutos de lectura

¿Como funciona exactamente la recursion de cola
alan coromano

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

  • recursión de cola es recursividad “normal”. Solo significa que la recursividad ocurre al final de la función.

    – Pete Becker

    20 de marzo de 2013 a las 11:27

  • … Pero se puede implementar de una manera diferente en el nivel de IL que la recursividad normal, reduciendo la profundidad de la pila.

    – KeithS

    20 de marzo de 2013 a las 14:17

  • Por cierto, gcc puede realizar la eliminación de recursión de cola en el ejemplo “normal” aquí.

    – dmckee — gatito ex-moderador

    20 de marzo de 2013 a las 16:58

  • @Geek: soy un desarrollador de C #, por lo que mi “lenguaje de ensamblaje” es MSIL o simplemente IL. Para C/C++, reemplace IL con ASM.

    – KeithS

    27 de marzo de 2013 a las 14:20


  • @ShannonSeverance Descubrí que gcc lo está haciendo por el simple recurso de examinar el código ensamblador emitido sin -O3. El enlace es para una discusión anterior que cubre un terreno muy similar y analiza lo que es necesario para implementar esta optimización.

    – dmckee — gatito ex-moderador

    27 de marzo de 2013 a las 23:42

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

  • @ Mr.32 No entiendo su pregunta. Convertí la función en una equivalente pero sin recursividad explícita (es decir, sin llamadas de función explícitas). Si cambia la lógica a algo no equivalente, puede hacer que la función se repita para siempre en algunos o en todos los casos.

    – Alexei Frunze

    20 de marzo de 2013 a las 9:30

  • Entonces la recursividad de las colas es efectiva solamente porque compilador optimizarlo? ¿Y de lo contrario sería lo mismo que una recursividad normal en términos de memoria de pila?

    – Alan Coromano

    20 de marzo de 2013 a las 9:48


  • Sí. Si el compilador no puede reducir la recursión a un bucle, está atascado con la recursión. Todo o nada.

    – Alexei Frunze

    20 de marzo de 2013 a las 9:57

  • @AlanDert: correcto. También puede considerar la recursión de cola como un caso especial de la “optimización de llamada de cola”, especial porque la llamada de cola es para la misma función. En general, cualquier llamada de cola (con los mismos requisitos sobre “no queda trabajo por hacer” que se aplican a la recursividad de cola, y donde el valor de retorno de la llamada de cola se devuelve directamente) se puede optimizar si el compilador puede realizar la llamada en un manera que configura la dirección de retorno de la función llamada para que sea la dirección de retorno de la función que realiza la llamada final, en lugar de la dirección desde la que se realizó la llamada final.

    –Steve Jessop

    20 de marzo de 2013 a las 9:59


  • @AlanDert en C, esto es solo una optimización que no aplica ningún estándar, por lo que el código portátil no debería depender de él. Pero hay lenguajes (Scheme es un ejemplo), en los que el estándar impone la optimización de recurrencia de cola, por lo que no debe preocuparse de que se desborde la pila en algunos entornos.

    –Jan Wrobel

    27 de marzo de 2013 a las 10:02

1646759952 598 ¿Como funciona exactamente la recursion de cola
lindybailarina

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.

  • Esta es una respuesta mucho mejor que las otras respuestas. Lo más probable es que el compilador no tenga un caso especial mágico para convertir el código recursivo de cola. Simplemente realiza una optimización de última llamada normal que pasa a ir a la misma función.

    – Arte

    20 de marzo de 2013 a las 12:10

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

  • No tan inteligente como la implementación de Alexey… y sí, eso es un cumplido.

    – Matthieu M.

    20 de marzo de 2013 a las 9:38

  • 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 eliminación de label/goto o simplemente tail call (ver la respuesta de Lindydancer).

    – Fob

    22 de marzo de 2013 a las 6:28


  • Si esto es todo recurrencia de cola, entonces ¿por qué la gente se emociona tanto al respecto? No veo a nadie entusiasmado con los bucles while.

    – Buh Buh

    24 de noviembre de 2013 a las 17:54

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

    – Pato mugido

    14 de noviembre de 2014 a las 1:26

¿Como funciona exactamente la recursion de cola
lucas ribeiro

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.

1646759952 648 ¿Como funciona exactamente la recursion de cola
Khaled.K

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

1646759953 415 ¿Como funciona exactamente la recursion de cola
Nursnaaz

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)

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

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)

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

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)

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

ingrese la descripción de la imagen aquí

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)

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

If bucle falla por lo que va a else lazo

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

If bucle falla por lo que va a else lazo

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

por lo que vuelve running_total

La salida para running_total = 24

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

ingrese la descripción de la imagen aquí

¿Como funciona exactamente la recursion de cola
iammilind

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.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad