Pregunta ¿Qué es la recursividad de cola?


Mientras comenzaba a aprender lisp, me encontré con el término recursivo de la cola. ¿Qué significa exactamente?


1294
2017-08-31 18:21


origen


Respuestas:


Considere una función simple que agrega los primeros N enteros. (p.ej. sum(5) = 1 + 2 + 3 + 4 + 5 = 15)

Aquí hay una implementación simple de JavaScript que usa la recursión:

function recsum(x) {
    if (x===1) {
        return x;
    } else {
        return x + recsum(x-1);
    }
}

Si llamaste recsum(5), esto es lo que evaluaría el intérprete de JavaScript:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Observe cómo se debe completar cada llamada recursiva antes de que el intérprete de JavaScript comience a hacer el trabajo de calcular la suma.

Aquí hay una versión recursiva de la misma función:

function tailrecsum(x, running_total=0) {
    if (x===0) {
        return running_total;
    } else {
        return tailrecsum(x-1, running_total+x);
    }
}

Aquí está la secuencia de eventos que ocurriría si llamaras tailrecsum(5), (que sería efectivamente tailrecsum(5, 0), debido al segundo argumento predeterminado).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

En el caso recursivo de cola, con cada evaluación de la llamada recursiva, el running_total esta actualizado

Nota: La respuesta original utilizó ejemplos de Python. Estos han sido cambiados a JavaScript, ya que los intérpretes de JavaScript modernos son compatibles optimización de la cola de llamada pero los intérpretes de Python no.


1292
2017-08-29 03:57



En recursión tradicional, el modelo típico es que primero realiza sus llamadas recursivas, y luego toma el valor de retorno de la llamada recursiva y calcula el resultado. De esta manera, no obtiene el resultado de su cálculo hasta que haya regresado de cada llamada recursiva.

En recursividad de la cola, primero realiza sus cálculos y luego ejecuta la llamada recursiva, pasando los resultados de su paso actual al siguiente paso recursivo. Esto resulta en la última declaración en forma de (return (recursive-function params)). Básicamente, el valor de retorno de cualquier paso recursivo dado es el mismo que el valor de retorno de la siguiente llamada recursiva.

La consecuencia de esto es que una vez que esté listo para realizar su próximo paso recursivo, ya no necesitará el marco de pila actual. Esto permite cierta optimización. De hecho, con un compilador escrito apropiadamente, nunca deberías tener un desbordamiento de pila risa disimulada con una llamada recursiva de cola. Simplemente reutilice el marco de pila actual para el siguiente paso recursivo. Estoy bastante seguro de que Lisp hace esto.


546
2017-08-31 17:29



Un punto importante es que la recursividad de la cola es esencialmente equivalente al bucle. No es solo una cuestión de optimización del compilador, sino un hecho fundamental sobre la expresividad. Esto es en ambos sentidos: puedes tomar cualquier ciclo del formulario

while(E) { S }; return Q

dónde E y Q son expresiones y S es una secuencia de enunciados y la convierte en una función recursiva de cola

f() = if E then { S; return f() } else { return Q }

Por supuesto, E, Sy Q tiene que definirse para calcular algún valor interesante sobre algunas variables. Por ejemplo, la función de bucle

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

es equivalente a la (s) función (es) recursiva (s) de cola

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Este "ajuste" de la función recursiva de cola con una función con menos parámetros es una expresión funcional común).


165
2017-08-29 16:03



Este extracto del libro Programación en Lua muestra cómo hacer una recursividad de cola adecuada (en Lua, pero también debe aplicarse a Lisp) y por qué es mejor.

UN llamada de cola [recursividad de la cola] es una especie de goto dressed   como una llamada. Una llamada final ocurre cuando   función llama a otro como su último   acción, por lo que no tiene nada más que hacer.   Por ejemplo, en el siguiente código,   la llamada a g es una llamada de cola:

function f (x)
  return g(x)
end

Después f llamadas g, no tiene nada más   que hacer. En tales situaciones, el programa   no necesita regresar a la llamada   función cuando la función llamada   termina. Por lo tanto, después de la llamada final,   el programa no necesita mantener ningún   información sobre la función de llamada   en la pila. ...

Porque una llamada de cola apropiada no usa   pila de espacio, no hay límite en el   número de llamadas de cola "anidadas" que   programa puede hacer. Por ejemplo, podemos   llama a la siguiente función con cualquier   número como argumento; nunca lo hará   desborda la pila:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

... Como dije antes, una llamada de cola es una   tipo de goto Como tal, un bastante útil   aplicación de llamadas de cola adecuadas en   Lua es para programar máquinas de estado.   Tales aplicaciones pueden representar cada   estado por una función; para cambiar el estado   es ir a (o llamar) a un   función. Como un ejemplo, déjenos   considera un simple juego de laberinto. El laberinto   tiene varias salas, cada una con hasta   cuatro puertas: norte, sur, este y   Oeste. En cada paso, el usuario ingresa un   dirección del movimiento Si hay una puerta   en esa dirección, el usuario va a   la habitación correspondiente; de lo contrario, el   programa imprime una advertencia. El objetivo es   pasar de una sala inicial a una final   habitación.

Este juego es una máquina de estado típica,   donde la habitación actual es el estado.   Podemos implementar tal laberinto con uno   función para cada habitación. Usamos cola   llamadas para pasar de una habitación a   otro. Un pequeño laberinto con cuatro habitaciones   podría verse así:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Como puede ver, cuando hace una llamada recursiva como:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Esto no es recursivo de cola porque todavía tiene cosas que hacer (agregar 1) en esa función después de realizar la llamada recursiva. Si ingresa un número muy alto, probablemente cause un desbordamiento de la pila.


110
2017-08-29 03:55



Usando la recursión regular, cada llamada recursiva empuja otra entrada a la pila de llamadas. Cuando se completa la recursión, la aplicación tiene que abrir cada entrada hasta que vuelva a bajar.

Con la recursividad de la cola, el compilador puede colapsar la pila hasta una entrada, por lo que se ahorra espacio en la pila ... Una consulta recursiva grande en realidad puede causar un desbordamiento de la pila.

Básicamente, las recurrencias de Tail se pueden optimizar en iteración.


57
2017-08-29 03:57



En lugar de explicarlo con palabras, he aquí un ejemplo. Esta es una versión de Scheme de la función factorial:

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

Aquí hay una versión de factorial que es recursiva de la cola:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Notará en la primera versión que la llamada recursiva al hecho se alimenta a la expresión de multiplicación y, por lo tanto, el estado debe guardarse en la pila cuando se realiza la llamada recursiva. En la versión recursiva de cola no hay otra expresión S esperando el valor de la llamada recursiva, y dado que no hay más trabajo por hacer, el estado no tiene que guardarse en la pila. Como regla, las funciones recursivas de la cola de Scheme usan un espacio de pila constante.


56
2017-08-29 07:21



El archivo de jerga tiene esto que decir acerca de la definición de recursividad de cola:

recursividad de la cola /norte./

Si ya no está harto de eso, vea recursividad de cola.


52
2017-08-29 03:57



La recursividad de cola se refiere a que la llamada recursiva es la última en la última instrucción lógica en el algoritmo recursivo.

Por lo general, en la recursión tienes un caso base que es lo que detiene las llamadas recursivas y comienza a abrir la pila de llamadas. Para usar un ejemplo clásico, aunque más C-ish que Lisp, la función factorial ilustra recursividad de cola. La llamada recursiva ocurre después verificando la condición del caso base.

factorial(x, fac) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Tenga en cuenta que la llamada inicial a factorial debe ser factorial (n, 1) donde n es el número para el que se debe calcular el factorial.


23
2017-08-31 23:52