La optimización de recursión de cola es un caso especial de optimización de llamadas de cola.
Se produce una llamada de cola cuando una función, [matemática] f [/ matemática], devuelve el valor de llamar a una función [matemática] f ‘[/ matemática] sin modificaciones. (Para las funciones nulas, [math] fv [/ math], se produce una llamada de cola cuando [math] fv [/ math] regresa inmediatamente después de llamar a una función [math] fv ‘[/ math].)
La optimización de la llamada de cola reconoce que el registro de activación (marco de pila) para la función [matemática] f [/ matemática] (o [matemática] fv [/ matemática]) ya no se utiliza cuando [matemática] f ‘[/ matemática] ([math] fv ‘[/ math]) se llama y se puede desasignar inmediatamente para que la función llamada [math] f’ [/ math] ([math] fv ‘[/ math]) pueda regresar directamente a la persona que llama [matemáticas] f [/ matemáticas] (o [matemáticas] fv [/ matemáticas]). O el marco de la pila puede reutilizarse, o modificarse ligeramente para reutilizarse, en cuyo caso la llamada a la función es realmente solo un goto. En cualquier caso, recibe una llamada de función sin necesidad de agregar otro registro de activación a la pila de llamadas.
- ¿Cuál es la forma más eficiente de verificar si un elemento es parte de un conjunto?
- Cómo resolver 735 / C en Codeforces
- ¿Por qué es 5n + 8n ^ 2 + 100n ^ 3 = O (n ^ 4)?
- ¿Por qué no usamos el aprendizaje automático para mejorar los modelos climáticos?
- ¿Cuán específicamente la memoria de la clase de almacenamiento cambiará las arquitecturas, los ecosistemas (incluidas las opciones de lenguaje de programación) y los algoritmos para big data?
Nadie dijo que [math] f [/ math] y [math] f ‘[/ math] no pueden ser la misma función (de manera similar para las funciones nulas). Una llamada recursiva se puede optimizar exactamente de la misma manera, ¡y el registro de activación definitivamente se verá igual! Simplemente asigne los argumentos en la llamada a los parámetros en el registro de activación de la función principal y vaya al inicio de la función.
Si todas las llamadas recursivas de una función son llamadas de cola, la función es recursiva de cola y se convertirá en un bucle, ejecutándose en un espacio de pila constante.
