language agnostic - ¿Qué es la eliminación de recurrencia de cola?

language-agnostic recursion

Question

Steve Yegge lo mencionó en una publicación de blog y no tengo idea de lo que significa, ¿podría alguien contarme?

¿Es lo mismo que la optimización de la cola de llamadas ?

Answer 1

La eliminación de llamada de cola es una optimización que ahorra espacio en la pila. Reemplaza una llamada de función con un goto . La eliminación de recurrencia de cola es la misma cosa, pero con la restricción adicional de que la función se está llamando a sí misma.

Básicamente, si lo último que hace una función A es return A(params...) entonces usted puede eliminar la asignación de un marco de pila y en su lugar establecer los registros apropiados y saltar directamente al cuerpo de la función.

Considere una convención de llamadas (imaginaria) que pase todos los parámetros en la pila y devuelva el valor en algún registro.

Algunas funciones podrían compilarse hasta (en un lenguaje ensamblador imaginario):

function:
//Reading params B, C, & D off the stack
pop B
pop C
pop D
//Do something meaningful, including a base case return
...
//Pass new values for B, C, & D to a new invocation of function on the stack
push D*
push C*
push B*
call function
ret

Lo que sea que lo anterior realmente haga, toma un marco de pila completamente nuevo para que funcione cada llamada. Sin embargo, dado que no ocurre nada después de la llamada de cola para funcionar, excepto un retorno, podemos optimizar de forma segura ese caso.

Resultando en:

function:
//Reading params B, C, & D off the stack (but only on the first call)
pop B
pop C
pop D
function_tail_optimized:
//Do something meaningful, including a base case return
...
//Instead of a new stack frame, load the new values directly into the registers
load B, B*
load C, C*
load D, D*
//Don''t call, instead jump directly back into the function
jump function_tail_optimized

El resultado final es una función equivalente que ahorra mucho espacio de pila, especialmente para entradas que dan como resultado un gran número de llamadas recursivas.

Se necesita mucha imaginación en mi respuesta, pero creo que puedes entender la idea.

Answer 2

desde here :

"... La eliminación de recurrencia de cola es un caso especial de eliminación de llamada de cola en el que la llamada de cola es una llamada a la función en sí. En ese caso, la llamada puede reemplazarse por un salto al inicio de la función después de mover los nuevos argumentos a los registros apropiados o ubicaciones de pila ... "

de Wikipedia :

"... Cuando se llama a una función, la computadora debe" recordar "el lugar desde donde fue llamada, la dirección de retorno, para que pueda regresar a esa ubicación con el resultado una vez que se complete la llamada. Normalmente, esta información se guarda en la pila, una lista simple de ubicaciones de retorno en orden de los tiempos en que se alcanzaron las ubicaciones de llamada que describen. A veces, lo último que hace una función después de completar todas las otras operaciones es simplemente llamar a una función, posiblemente a sí misma, y ​​regresar su resultado. Con la recursividad final, no hay necesidad de recordar el lugar desde el que llamamos, en su lugar, podemos dejar la pila solo, y la función recién llamada devolverá su resultado directamente al llamador original. Convirtiendo una llamada a una sucursal o saltar en un caso así se llama optimización de la cola de llamadas. Tenga en cuenta que la llamada de la cola no tiene que aparecer léxicamente después de todas las otras declaraciones en el código fuente, es importante que su resultado se devuelva inmediatamente, ya que la función de llamada wil Nunca tengo la oportunidad de hacer nada después de la llamada si la optimización se realiza ... "