lisp - recursivo - ¿Cuál es la diferencia entre las llamadas de cola y la recursión de cola?
recursividad programacion (3)
Entiendo que la recursión de la cola, es un caso especial en el que una función realiza llamadas de cola a sí misma. Pero no entiendo cómo las llamadas de cola y la recursión de cola son diferentes. En lenguaje "recursivo de cola correctamente" con TCO (Optimización de llamadas de cola) implementado, como Scheme, significa que las llamadas de cola y la recursión de cola no consumen pila u otros recursos. En un lenguaje en el que el compilador no puede optimizar la recursión de la cola, el programa puede quedarse sin pila y fallar. En los lenguajes "correctamente recursivos de la cola", la implementación de la recursión de la cola para el bucle no es menos eficiente que el uso de un bucle, supongo.
Bueno, los dos están relacionados de alguna manera, ya que ambos tienen la palabra ''cola'' en ellos, pero son completamente diferentes ...
La recursión de cola es una recursión con algunas restricciones específicas, y las llamadas de cola son llamadas de función. Su pregunta es un poco como "¿Cuál es la diferencia entre un animal y un gato?" ...
Una llamada de cola es una llamada de función en la posición de cola. Ejemplos: f(x) en f(x) , y g(★) en g(f(x)) Ejemplos de contador: f(x) en 1+f(x) y en g(f(x))
La recursión de cola es una recursión donde las llamadas recursivas son llamadas de cola. Ejemplos: f(★) a la derecha del signo "=" en f(x) = f(x) , f(x,y) = if x == 0 then y else f(x-1,y+x) He definido dos funciones recursivas que se llaman a sí mismas con llamadas de cola. Eso es.
En los idiomas con TCO, las llamadas a la cola no cuestan nada, por lo que la recursión (cola) funciona en una pila constante, y todos están contentos.
Como usted dice, la recursión de cola es un caso especial de una llamada de cola. En consecuencia, cualquier lenguaje que implemente TCO general de forma trivial es "correctamente recursivo de la cola".
Lo inverso, sin embargo, no se sostiene. Hay bastantes idiomas que solo optimizan la recursión de la cola, ya que es mucho más fácil: puede traducirlo directamente a un bucle, y no necesita una operación específica de "llamada de la cola" que manipule la pila de nuevas maneras. Por ejemplo, esa es la razón por la que los idiomas que compilan en la JVM, que no tienen una instrucción de llamada de cola, generalmente solo optimizan la recursión (auto) de cola. (Existen técnicas para evitar la falta de tal instrucción, por ejemplo, camas elásticas, pero son bastante caras).
La optimización de la llamada de cola completa no solo se aplica a las llamadas recursivas propias (o mutuamente), sino a cualquier llamada en la posición de cola. En particular, se extiende a las llamadas cuyo destino no se conoce de forma estática , por ejemplo, cuando se invoca una función de primera clase o un método de envío dinámico. En consecuencia, requiere técnicas de implementación algo más elaboradas (aunque conocidas).
Muchas técnicas de programación funcional, pero también algunos patrones OO populares (consulte, por ejemplo, la presentación ECOOP''04 de Felleisen o la publicación del blog de Guy Steele ), requieren un TCO completo para poder ser utilizados.
Desambiguemos "llamadas de cola" primero.
Una llamada en posición de cola es una llamada de función cuyo resultado se devuelve inmediatamente como el valor de la función de encierro. La posición de cola es una propiedad estática.
Se puede implementar una llamada en la posición final sin empujar nada en la pila, porque el marco de pila antiguo es esencialmente inútil (bajo supuestos que generalmente son verdaderos en lenguajes funcionales pero no necesariamente en C, etc.). Como lo dijo Guy Steele, una llamada de cola es un salto que pasa argumentos.
A grandes rasgos, una implementación de lenguaje es adecuadamente recursiva de cola si tiene el mismo uso de espacio asintótico que una que implementa todas las llamadas en posición de cola como saltos sin crecimiento de pila. Esa es una simplificación realmente áspera. Si desea ver la historia completa, vea Recursión de cola adecuada y eficiencia en el espacio de Clinger.
Tenga en cuenta que el solo manejo de las funciones recursivas de la cola no es suficiente para lograr la recursión de la cola adecuada ( cualquier llamada de la cola debe ser manejada especialmente). La terminología es algo engañosa.
También tenga en cuenta que hay otras formas de lograr esa eficiencia de espacio asintótica sin implementar llamadas de cola como saltos. Por ejemplo, puede implementarlas como llamadas normales y luego compactar periódicamente la pila eliminando marcos inútiles (de alguna manera). Ver Cheney de Baker en la MTA .