L'itération peut remplacer la récursivité?

J'ai vu partout débordement de pile, par exemple ici , ici , ici , ici , ici et quelques autres que je me fiche de mentionner, que "tout programme qui utilise la récursion peut être converti en un programme utilisant uniquement l'itération".

Il y avait même un fil de discussion très élevé avec une réponse très positive qui disait oui, c'est possible.

Maintenant, je ne dis pas qu'ils ont tort. C'est juste que cette réponse contredit mes maigres connaissances et ma compréhension de l'informatique.

Je crois que chaque fonction itérative peut être exprimée en tant que récursivité, et Wikipedia a une déclaration à cet effet. Cependant, je doute que l'inverse soit vrai. D'une part, je doute que les fonctions récursives non primitives puissent être exprimées de manière itérative.

Je doute aussi que les hyper-opérations puissent être exprimées de manière itérative.

Dans sa réponse (que je ne comprends pas, par ailleurs) à ma question, @YuvalFIlmus a déclaré qu'il n'était pas possible de convertir une séquence d'opérations mathématiques en une séquence d'ajouts.

Si la réponse de YF est effectivement correcte (je suppose que oui, mais son raisonnement était au-dessus de ma tête), cela ne signifie-t-il pas que toutes les récursions ne peuvent pas être converties en itération? Parce que s'il était possible de convertir chaque récursivité en itération, je serais capable d'exprimer toutes les opérations sous forme d'une séquence d'ajouts.

Ma question est la suivante:

Chaque récursivité peut-elle être convertie en itération et pourquoi?

Veuillez donner une réponse à un brillant lycéen ou à un étudiant de première année comprendra. Merci.

PS Je ne sais pas ce qu'est la primitive récursive (je connais la fonction Ackermann, et ce n'est pas une récursive primitive, mais elle est toujours calculable. Toutes mes connaissances à ce sujet proviennent de la page Wikipedia sur la fonction Ackermann.)

PPS: Si la réponse est oui, pourriez-vous par exemple écrire une version itérative d'une fonction non primitive-récursive. Par exemple Ackermann dans la réponse. Ça m'aidera à comprendre.

Il est possible de remplacer la récursion par itération plus une mémoire illimitée .

Si vous avez seulement une itération (par exemple, while loops) et une quantité finie de mémoire, tout ce que vous avez est un automate fini. Avec une quantité de mémoire finie, le calcul a un nombre fini d'étapes possibles, il est donc possible de les simuler avec un automate fini.

Avoir une mémoire illimitée change la donne. Cette mémoire sans limite peut prendre de nombreuses formes qui se révèlent avoir un pouvoir expressif équivalent. Par exemple, une machine de Turing reste simple: il n'y a qu'une seule bande et l'ordinateur ne peut avancer ou reculer sur la bande que d'une étape à la fois - mais cela suffit pour faire tout ce que vous pouvez faire avec des fonctions récursives.

Une machine de Turing peut être vue comme un modèle idéalisé d’ordinateur (machine à états finis) avec un espace de stockage supplémentaire qui augmente à la demande. Notez qu'il est crucial non seulement qu'il n'y ait pas de limite finie sur la bande, mais même en tenant compte de l'entrée, vous ne pouvez pas prédire de manière fiable la quantité de bande nécessaire. Si vous pouviez prédire (c.-à-d. Calculer) combien de bande est nécessaire à partir de l'entrée, vous pourriez alors décider si le calcul serait interrompu en calculant la taille maximale de la bande, puis en considérant l'ensemble du système, y compris la bande désormais finie, comme une machine à états finis. .

Une autre façon de simuler une machine de Turing avec des ordinateurs est la suivante. Simulez la machine de Turing avec un programme informatique qui enregistre le début de la bande en mémoire. Si le calcul atteint la fin de la partie de la bande qui tient dans la mémoire, remplacez l'ordinateur par un ordinateur plus grand et exécutez à nouveau le calcul.

Supposons maintenant que vous souhaitiez simuler un calcul récursif avec un ordinateur. Les techniques d'exécution de fonctions récursives sont bien connues: chaque appel de fonction dispose d'une mémoire, appelée frame de pile . De manière cruciale, les fonctions récursives peuvent propager des informations à travers plusieurs appels en transmettant des variables. En termes de mise en œuvre sur un ordinateur, cela signifie qu'un appel de fonction peut accéder à la trame de pile d'un appel (grand) ^* parent.

Un ordinateur est un processeur - une machine à états finis (avec un grand nombre d'états, mais nous appliquons la théorie du calcul ici, donc tout ce qui compte, c'est qu'il soit fini) - couplé à une mémoire finie. Le microprocesseur exécute une boucle géante while: «tant que l'appareil est sous tension, lisez une instruction dans la mémoire et exécutez-la». (Les vrais processeurs sont beaucoup plus complexes que cela, mais cela n’affecte pas ce qu’ils peuvent calculer, mais leur rapidité et leur facilité de le faire.) Un ordinateur peut exécuter des fonctions récursives avec juste cette boucle while pour fournir une itération, plus le mécanisme pour accéder à la mémoire, y compris la possibilité d’augmenter la taille de la mémoire à volonté.

Si vous limitez la récursivité à la récursion primitive, vous pouvez limiter l'itération à l' itération liée . C'est-à-dire qu'au lieu d'utiliser des boucles while avec un temps d'exécution imprévisible, vous pouvez utiliser des boucles for pour lesquelles le nombre d'itérations est connu au début de la boucle¹. Le nombre d'itérations peut ne pas être connu au début du programme: il peut lui-même avoir été calculé par les boucles précédentes.

Je ne vais même pas esquisser une preuve ici, mais il existe une relation intuitive entre le passage d'une récursion primitive à une récursion complète et le passage d'une boucle à l'autre: dans les deux cas, il est impossible de savoir à l'avance Arrêtez. Avec la récursion complète, cela est fait avec l'opérateur de minimisation, où vous continuez jusqu'à ce que vous trouviez un paramètre qui satisfait à la condition. Avec les boucles while, ceci est fait en continuant jusqu'à ce que la condition de boucle soit remplie.

_forwhile$n$

Chaque récursion peut être convertie en itération, comme en témoigne votre CPU, qui exécute des programmes arbitraires à l'aide d'une itération infinie fetch-execute. C'est une forme du théorème de Böhm-Jacopini . De plus, de nombreux modèles de calcul complets de Turing n'ont pas de récursivité, par exemple les machines de Turing et les machines de comptage .

Les fonctions récursives primitives correspondent aux programmes utilisant l' itération liée , c'est-à-dire que vous devez spécifier le nombre d'itérations qu'une boucle est exécutée à l'avance. L'itération délimitée ne peut généralement pas simuler la récursivité, car la fonction Ackermann n'est pas récursive primitive. Mais une itération non bornée peut simuler toute fonction partiellement calculable.

$a(n,m)$

$s$

$\DeclareMathOperator{\push}{push}\push(s, x)$$x$$\DeclareMathOperator{\pop}{pop} x ← \pop(s)$$\DeclareMathOperator{\empty}{empty}\empty(s)$

$\texttt{Ackermann}(n_0, m_0):$ $\def\ifop#1{\texttt{if(}#1\texttt{):}}$ $\def\elseif#1{\texttt{else if(}#1\texttt{):}}$ $\def\elsop{\texttt{else:}}$

• $s = \emptyset$ (initialise la pile vide)
• $\push(s,n_0)$
• $\push(s,m_0)$
• $\texttt{while(true):}$
  • $m ← \pop(s)$
  • $\ifop{\empty(s)}$
    • $\texttt{return }m$ (cela termine la boucle)
  • $n ← \pop(s)$
  • $\ifop{n = 0}$
    • $\push(s, m+1)$
  • $\elseif{m=0}$
    • $\push(s, n-1)$
    • $\push(s, 1)$
  • $\elsop$
    • $\push(s, n-1)$
    • $\push(s, n)$
    • $\push(s, m-1)$

Je l'ai implémenté à Ceylan, vous pouvez l' exécuter dans le WebIDE , si vous le souhaitez. (Il sort la pile au début de chaque itération de la boucle.)

Bien sûr, cela vient de déplacer la pile d'appels implicites de la récursivité vers une pile explicite avec les paramètres et les valeurs de retour.

Il y a déjà quelques bonnes réponses (que je ne peux même pas espérer concurrencer), mais j'aimerais proposer cette explication simple.

La récursivité est simplement la manipulation de la pile d'exécution. Récursif ajoute un nouveau cadre de pile (pour le nouvel appel de la fonction récursive), et le retour supprime un cadre de pile (pour l'innovation récemment complétée de la fonction récursive). La récursivité entraîne l'ajout / la suppression d'un certain nombre de trames de pile, jusqu'à ce qu'elles finissent toutes par sortir (si tout va bien!) Et que le résultat soit renvoyé à l'appelant.

Maintenant, que se passerait-il si vous créiez votre propre pile, remplaçiez les appels de fonctions récursifs en poussant vers la pile, remplacions le renvoi depuis des fonctions récursives par le vidage de la pile et si une boucle while s'exécutait jusqu'à ce que la pile soit vide?

Autant que je sache, et selon ma propre expérience, vous pouvez implémenter toute récursion sous forme d'itération. Comme mentionné ci-dessus, la récursivité utilise la pile, qui est conceptuellement illimitée, mais pratiquement limitée (avez-vous déjà reçu un message de débordement de pile?). À mes débuts en programmation (au troisième quart du dernier siècle du dernier millénaire), j'utilisais des langages non récursifs implémentant des algorithmes récursifs et je n'avais aucun problème. Je ne sais pas comment on pourrait le prouver, cependant.