La capacité de récursivité fonction du processeur ou la langue de programmation / compilateur ou les deux?

Question

est la possibilité d'appeler une fonction récursive une capacité inhérente du processeur ou la langue / compilateur de programmation. Peut-être, les deux ont besoin des éléments pour soutenir récursion?

J'ai toujours été sous l'impression que la possibilité d'appeler une fonction récursive est purement mis en œuvre dans le langage de programmation et de la façon dont elle dispose sa pile d'exécution jusqu'à quand et où revenir. Ai-je raison de supposer ou faire des processeurs donc ont une logique spécifique qui permet récursion?

Answer 1

Un processeur saute à l'endroit où le code indique à. Récursion est certainement une fonction linguistique.

Il est fonction du compilateur aussi, dans la mesure où le compilateur doit mettre en œuvre la langue. Mais si elle ne l'a pas, nous avions considérons cassé.

Enfin, bien sûr, la charge de l'opération est pris en charge par le processeur: il doit pousser le contexte et les variables sur un cadre de pile, sauter au point d'entrée d'une routine, exécutez les instructions, revenez ... vous savez, les choses un processeur fait.

Answer 2

Tous les processeurs modernes sont capables de récursion parce qu'ils ont appel de fonction et de retour des instructions qui sont basées sur une pile.

ordinateurs antérieures avaient un temps très difficile de celui-ci. Par exemple, IBM 360 disposé code de sorte que la valeur de retour et les variables locales de la fonction étaient à côté du code. Un appel récursif écraserait les valeurs de l'appel précédent.

Answer 3

Langue.

Vous ne même pas toujours besoin d'une pile à récursif. Voir récursion de queue pour un exemple d'un type de récursion qui n'a pas besoin d'une pile.

Answer 4

Comme Carl Smotricz dit, une unité centrale de traitement suit juste les instructions de branchement qui se produisent dans le flux d'instructions. Ce que nous avons tendance à appeler récursion est rien plus que les appels de fonction ordinaire, où la fonction appelée se trouve être le même que celui en cours d'exécution, ce qui, à un niveau élevé, a des effets très intéressants.

Answer 5

Même sur les processeurs modernes avec des modes d'adressage de la pile, vous voulez encore parfois d'allouer des trames d'appel sur le tas, comme cela a été fait sur des systèmes tels que OS / 360. Par exemple, dans le schéma, il est possible de capturer une suite (essentiellement un cadre d'appel en plus d'une représentation des liaisons de variables locales actives) et garder la main de celui-ci. Si vous capturez une continuation dans une variable globale dans une fonction, puis revenez de cette fonction, le cadre de l'appel actif ne peut pas être nettoyé. Il sera nettoyé par le collecteur des ordures à un moment donné, une fois qu'il n'y a plus de références à, mais en attendant, si le cadre d'appel a été alloué sur la pile, il doit être copié dans un autre (le tas). C'est un peu à l'opposé de l'optimisation des appels de queue, où vous pouvez prouver que vous ne devez jamais affecter le cadre de pile pour un appel récursif. Pour une suite, vous devez allouer le cadre d'appel et de le conserver et de son environnement associé indéfiniment traîner.

Answer 6

Vous n'avez pas besoin d'un soutien matériel explicite pour une pile et des appels récursifs, mais le processeur a besoin de certaines capacités. Je pense que ce qui suit est suffisante sur une machine basée sur un registre:

• Vous pouvez écrire une valeur stockée au compteur de programme, par exemple avec une instruction de saut. Cela est nécessaire pour revenir.
• Vous pouvez vous permettre d'utiliser un registre stockant votre propre pointeur de pile.
• Interruptions pas les choses gâcher trop mal (mais vous pouvez peut-être vivre avec ne pas avoir pile dans un contexte d'interruption, même si elles le font).

Code Bootstrap doit assigner une région de mémoire à utiliser comme pile, et le tour est joué.

Je suppose que quelques processeurs ne fournissent pas. La plupart des processeurs ont un soutien explicite pour un pointeur de pile et un pointeur de lien et des instructions qui aident à la convention d'appel standard. Mais vous peut inventer et mettre en œuvre votre propre convention d'appel.