¿Qué es la recursividad de la cola?

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

 int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } 

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

 int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; } 

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

La recursividad de 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 sea 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 inmediatamente, por lo que podemos omitir la cadena completa de funciones recursivas que regresan y regresar directamente al llamador original. Eso significa que no «No necesito una pila de llamadas para todas las llamadas recursivas, y puedo implementar la llamada final como un simple salto, lo que nos ahorra espacio.

Comentarios

• escribiste » Eso significa que no ‘ no necesitamos una pila de llamadas para todas las llamadas recursivas «. La pila de llamadas siempre estará ahí, solo que la dirección de retorno no necesita escribirse en la pila de llamadas, ¿verdad?
• Depende de su modelo de cálculo hasta cierto punto 🙂 Pero sí, en una computadora real el la pila de llamadas todavía está allí, ‘ simplemente no la estamos usando.
• ¿Qué pasa si ‘ es el llamar pero en bucle for. Por lo tanto, realiza todos los cálculos anteriores, pero algunos de ellos en un bucle for como def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – este no ‘ t termina.

Dicho simplemente, la recursividad de cola es una recursividad donde 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, el diseño de 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 de cola recursiva:

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

Pero esto es una cola- función recursiva:

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

«. Pero esto se puede hacer solo si el valor devuelto por la llamada recursiva se devuelve directamente.

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

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

Enfoque A: Proceso lineal recursivo

(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 Enfoque B tiene este aspecto:

(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 (método B) se ejecuta en un espacio constante, aunque el proceso es un procedimiento recursivo. También debe tenerse en cuenta que en este enfoque un conjunto de variables definen el estado del proceso en cualquier punto, a saber. {product, counter, max-count}. Esta es también una técnica por la cual la recursividad de cola permite la optimización del compilador.

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

Comentarios

• No debería ‘ ser solo (1) en lugar de (* 1)?

Tail-recursión es una forma de recursividad en la que las llamadas recursivas son las últimas instrucciones en la función (de donde proviene la parte de la cola). Además, la llamada recursiva no debe componerse con referencias a celdas de memoria que almacenan 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; tail-recursive es una forma de optimizar los algoritmos recursivos. La otra ventaja / optimización es que hay una manera fácil de transformar un algoritmo recursivo de cola en uno equivalente que usa iteración en lugar de recursividad. Así que sí, el algoritmo de ordenación rápida es recursivo de cola.

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