¿Qué es la recursividad de la cola?

52

Conozco el concepto general de recursión. Encontré el concepto de recursión de la cola mientras estudiaba el algoritmo de clasificación rápida. En este video del algoritmo de clasificación rápida del MIT a las 18:30 segundos, el profesor dice que este es un algoritmo recursivo de cola. No me queda claro qué significa realmente la recursión de la cola.

¿Alguien puede explicar el concepto con un ejemplo adecuado?

Algunas respuestas proporcionadas por la comunidad SO aquí .

Friki
fuente
Cuéntanos más sobre el contexto en el que has encontrado el término recursión de cola . ¿Enlazar? ¿Citación?
A.Schulz
@ A.Schulz He puesto el enlace al contexto.
Geek
55
Mire " ¿Qué es la recursividad de la cola? " En stackoverflow
Vor
2
@ajmartin La pregunta está en el límite de Stack Overflow pero firmemente en el tema de informática , por lo que en principio la informática debería producir mejores respuestas. No ha sucedido aquí, pero aún está bien volver a preguntar aquí con la esperanza de una mejor respuesta. Geek, deberías haber mencionado tu pregunta anterior sobre SO, para que la gente no repita lo que ya se ha dicho.
Gilles 'SO- deja de ser malvado'
1
También debe decir cuál es la parte ambigua o por qué no está satisfecho con las respuestas anteriores, creo que en SO las personas brindan buenas respuestas, pero ¿qué le hizo volver a preguntar?

Respuestas:

52

La recursividad de cola es un caso especial de recursión donde la función de llamada no realiza más cálculos después de hacer una llamada recursiva. Por ejemplo, la función

int f (int x, int y) {
  si (y == 0) {
    volver x;
  }

  devuelve f (x * y, y-1);
}

es recursiva de cola (ya que la instrucción final es una llamada recursiva) mientras que esta función no es recursiva de cola:

int g (int x) {
  si (x == 1) {
    retorno 1;
  }

  int y = g (x-1);

  devolver x * y;
}

ya que hace algunos cálculos después de que la llamada recursiva ha regresado.

La recursividad de la cola es importante porque se puede implementar de manera más eficiente que la recursividad general. Cuando hacemos una llamada recursiva normal, tenemos que insertar la dirección de retorno en la pila de llamadas y luego saltar a la función llamada. Esto significa que necesitamos una pila de llamadas cuyo tamaño es lineal en la profundidad de las llamadas recursivas. Cuando tenemos una recursividad de cola, sabemos que tan pronto como regresemos de la llamada recursiva, también regresaremos de inmediato, para que podamos omitir toda la cadena de funciones recursivas que regresan y regresar directamente a la persona que llama original. Eso significa que no necesitamos una pila de llamadas para todas las llamadas recursivas, y podemos implementar la llamada final como un simple salto, lo que nos ahorra espacio.

Matt Lewis
fuente
2
usted escribió "Eso significa que no necesitamos una pila de llamadas para todas las llamadas recursivas". La pila de llamadas siempre estará allí, solo que la dirección de retorno no necesita escribirse en la pila de llamadas, ¿verdad?
Geek
2
Depende de su modelo de cálculo hasta cierto punto :) Pero sí, en una computadora real la pila de llamadas todavía está allí, simplemente no la estamos usando.
Matt Lewis
¿Qué pasa si es la última llamada pero for for loop? Así que haces todos tus cálculos anteriores, pero algunos de ellos en un bucle for comodef recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
thed0ctor el
13

Simplemente dicho, la recursión de cola es una recursión en la que el compilador podría reemplazar la llamada recursiva con un comando "goto", por lo que la versión compilada no tendrá que aumentar la profundidad de la pila.

A veces, diseñar una función recursiva de cola requiere que necesite crear una función auxiliar con parámetros adicionales.

Por ejemplo, esta no es una función recursiva de cola:

int factorial(int x) {
    if (x > 0) {
        return x * factorial(x - 1);
    }
    return 1;
}

Pero esta es una función recursiva de cola:

int factorial(int x) {
    return tailfactorial(x, 1);
}

int tailfactorial(int x, int multiplier) {
    if (x > 0) {
        return tailfactorial(x - 1, x * multiplier);
    }
    return multiplier;
}

porque el compilador podría reescribir la función recursiva a una no recursiva, usando algo como esto (un pseudocódigo):

int tailfactorial(int x, int multiplier) {
    start:
    if (x > 0) {
        multiplier = x * multiplier;
        x--;
        goto start;
    }
    return multiplier;
}

La regla para el compilador es muy simple: cuando encuentre " return thisfunction(newparameters);", reemplácelo con " parameters = newparameters; goto start;". Pero esto solo se puede hacer si el valor devuelto por la llamada recursiva se devuelve directamente.

Si todas las llamadas recursivas en una función se pueden reemplazar de esta manera, entonces es una función recursiva de cola.

Viliam Búr
fuente
13

Mi respuesta se basa en la explicación dada en el libro Estructura e interpretación de programas de computadora . Recomiendo este libro a los científicos informáticos.

Enfoque A: proceso recursivo lineal

(define (factorial n)
 (if (= n 1)
  1
  (* n (factorial (- n 1)))))

La forma del proceso para el Enfoque A se ve así:

(factorial 5)
(* 5 (factorial 4))
(* 5 (* 4 (factorial 3)))
(* 5 (* 4 (* 3 (factorial 2))))
(* 5 (* 4 (* 3 (* 2 (factorial 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

Enfoque B: proceso iterativo lineal

(define (factorial n)
 (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
 (if (> counter max-count)
  product
  (fact-iter (* counter product)
             (+ counter 1)
             max-count)))

La forma del proceso para el Enfoque B se ve así:

(factorial 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120

El proceso iterativo lineal (enfoque B) se ejecuta en un espacio constante a pesar de que el proceso es un procedimiento recursivo. También debe tenerse en cuenta que, en este enfoque, un conjunto de variables define el estado del proceso en cualquier punto, a saber. {product, counter, max-count}. Esta es también una técnica mediante la cual la recursividad de cola permite la optimización del compilador.

En el Enfoque A, hay más información oculta que el intérprete mantiene, que es básicamente la cadena de operaciones diferidas.

ajmartin
fuente
5

La recursividad de cola es una forma de recursión en la que las llamadas recursivas son las últimas instrucciones de la función (de ahí proviene la parte de cola). Además, la llamada recursiva no debe estar compuesta con referencias a celdas de memoria que almacenen valores anteriores (referencias distintas de los parámetros de la función). De esta manera, no nos importan los valores anteriores y un marco de pila es suficiente para todas las llamadas recursivas; la recursividad de cola es una forma de optimizar algoritmos recursivos. La otra ventaja / optimización es que hay una manera fácil de transformar un algoritmo recursivo de cola a uno equivalente que usa iteración en lugar de recursividad. Entonces sí, el algoritmo para quicksort es realmente recursivo.

QUICKSORT(A, p, r)
    if(p < r)
    then
        q = PARTITION(A, p, r)
        QUICKSORT(A, p, q–1)
        QUICKSORT(A, q+1, r)

Aquí está la versión iterativa:

QUICKSORT(A)
    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        r = q - 1

    p = 0, r = len(A) - 1
    while(p < r)
        q = PARTITION(A, p, r)
        p = q + 1
saadtaame
fuente