¿El manejo de la recursión necesita un tratamiento especial al diseñar un compilador?

Question

Las llamadas de funciones se manejan a través de una estructura de datos de pila. ¿Es esto suficiente para apoyar la recursión?

Answer 1

Tener la pila es El tratamiento especial que el compilador tiene que tener al respaldar la recursión.

En lenguajes de programación anteriores como las primeras versiones de Fortran, el entorno de tiempo de ejecución no tenía una pila de funciones y cada función tenía exactamente un registro de activación reservado para él en algún lugar de la memoria. Eso significaba que la recursión no era posible en absoluto, porque si recursivamente se llamaba una función, sobrescribiría su único registro de activación, perdiendo la pista del contexto de cómo llegó allí.

La introducción de la pila de funciones es lo que primero permitió que la recursión se exprese realmente en un lenguaje de programación. Antes de eso, los programadores usarían la recursión como una herramienta para resolver abstractamente un problema, pero luego tendrían que traducir ese código en lógica iterativa debido a la falta de una pila de llamadas.

Para que un lenguaje de programación admita la recursión, debe tener algún mecanismo para mantener dinámicamente la pila de llamadas. Esto no tiene que ser a través de una pila explícita; En teoría, podría alquilar dinámicamente todos los marcos de pila y encadenarlos como una lista vinculada. Esto puede ser útil, por ejemplo, si desea admitir coroutinas o cierres y realmente necesita mantener registros de activación antiguos después de que la función regrese para que los datos se puedan almacenar más adelante.

¡Espero que esto ayude!