¿La capacidad de recursividad es una función del procesador, del lenguaje de programación/compilador o de ambos?

Question

¿Es la capacidad de llamar recursivamente a una función una capacidad inherente del procesador o del lenguaje de programación/compilador?¿Quizás ambos necesitan elementos para soportar la recursividad?

Siempre he tenido la impresión de que la capacidad de llamar recursivamente a una función se implementa puramente en el lenguaje de programación y en cómo presenta su pila de tiempo de ejecución en cuanto a cuándo y dónde regresar.¿Estoy en lo cierto al suponerlo o los procesadores tienen una lógica específica que permite la recursividad?

Answer 1

Un procesador simplemente salta en el que el código le dice que lo haga. La recursividad es definitivamente una función del lenguaje.

Es una función de compilación también, en la medida en que el compilador tiene que poner en práctica el idioma. Pero entonces, si no lo hizo, nos consideramos roto.

Por último, por supuesto, la carga de la operación está soportada por el procesador: tiene que empujar el contexto y las variables en un marco de pila, salta al punto de entrada una rutina, ejecutar las instrucciones, volver ... ya sabes, las cosas un procesador hace.

Answer 2

Todos los procesadores modernos son capaces de recurrir a la recursividad porque tienen instrucciones de llamada y devolución de funciones basadas en pila.

Las computadoras anteriores lo pasaron muy mal.Por ejemplo, IBM 360 dispuso el código de modo que el valor de retorno y las variables locales de la función estuvieran junto al código.Una llamada recursiva afectaría los valores de la llamada anterior.

Answer 3

Idioma.

Incluso no siempre se necesita una pila para recursivo. Ver recursión de cola para un ejemplo de un tipo de recursividad que no necesita una pila.

Answer 4

Como dijo Carl Smotricz, una CPU se limita a seguir las instrucciones de ramificación que se producen en el flujo de instrucciones. Lo que solemos llamar la recursividad es no más de llamadas a funciones ordinarias, donde la función se llama pasa a ser la misma que la ejecución de la actualidad, lo que, en un alto nivel, tiene algunos efectos muy interesantes.

Answer 5

Incluso en los procesadores modernos con los modos de direccionamiento de pila, que todavía a veces se desea asignar marcos de llamadas en el montón, como se hizo en sistemas como OS / 360. Por ejemplo, en el esquema, es posible capturar una continuación (básicamente un marco de llamada más una representación de las asociaciones de variables locales activas) y mantener la suspensión de la misma. Si se captura una continuación en una variable global dentro de una función, y luego regrese de esa función, el marco de llamada activa no se puede limpiar. Que será limpiado por el recolector de basura en algún momento, una vez que ya no hay ninguna referencia a ella, pero mientras tanto, si el marco de llamada se asigna en la pila, que necesita ser copiado en otro lugar (la pila). Esta es una especie de lo contrario de optimización llamada de cola, donde se puede probar que usted nunca tiene que asignar el marco de pila para una llamada recursiva. Para una continuación, es necesario asignar el marco de llamada y mantenerlo y su entorno asociado dando vueltas indefinidamente.

Answer 6

No es necesario el soporte de hardware explícita para una pila y las llamadas recursivas, pero el procesador no necesita ciertas capacidades. Creo que la siguiente es suficiente en una máquina basada en el registro:

• Usted puede escribir un valor almacenado en el contador de programa, por ejemplo, con una instrucción de salto. Esto es necesario para volver.
• Puede permitirse el uso de un registro almacenar su propio puntero de pila.
• Las interrupciones No desordenar las cosas tan mal (aunque tal vez se puede vivir con tener ninguna pila en el contexto de interrupciones incluso si lo hacen).

código de arranque tiene que asignar una región de la memoria para su uso como pila, y ya está.

supongo unos procesadores no ofrecen esto. La mayoría de los procesadores tienen un apoyo explícito a un puntero de pila y un puntero de enlace, y las instrucciones que ayudan con la convención de llamada estándar. Pero usted podría inventar y poner en práctica su propia convención de llamada.