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

42

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.

Tobi Alafin
la source
21
Tout ce que vous exécutez sur un processeur est itératif. Vous pouvez l'écrire de manière récursive dans un langage d'ordre supérieur, mais il est néanmoins compilé dans un tas d'instructions d'assembleur itératif. Donc, littéralement, le compilateur fait exactement ce que vous demandez, il convertit toute votre récursion sophistiquée en un tas d'instructions itératives pour un processeur.
Davor
6
Sur un niveau bas, la plupart d'entre nous savons que la récursivité est égale à l'itération plus la pile. La récursion des modèles de grammaires sans contexte, tandis que les automates à pile sont des "programmes" itératifs avec de la mémoire de pile.
Hendrik janv
2
En soulignant que c’est généralement une bonne idée d’attendre au moins 24 heures pour voir si d’autres réponses apparaissent. La question acceptée me semble franchement très compliquée et compliquée, et semble délibérément compliquer les choses plus que nécessaire. La réponse de base à votre question est "la pile utilisée pour la récursion peut être implémentée de manière explicite de manière itérative", et il n’est pas nécessaire que ce soit beaucoup plus compliqué que cela. Les considérations sur le fait que la mémoire soit sans limite ou non entrent en jeu, car cette fonctionnalité est également nécessaire pour les piles de récursivité.
AnoE
il est possible d'implémenter l'émulateur de machine de Turing avec une seule itération
Sarge Borsch
Dans un cours comparatif de langues que j’avais suivi il y a longtemps, nous devions écrire la fonction d’Ackermann en assembleur, en FORTRAN (pas en Fortran moderne) et dans un langage de choix récursif. Alors oui, c'est possible dans la pratique. Et bien sûr, c'est possible en théorie. Voir, par exemple, la question prouve que les machines de Turing et le lambda calcul sont équivalents .
David Hammen

Réponses:

52

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.

forwhilen

Gilles, arrête de faire le mal
la source
Accepter pour l'explication détaillée, maintenu au niveau demandé.
Tobi Alafin
12
Je pense que cela vaut la peine de noter que dans les ordinateurs réels, la récursivité utilise également de la mémoire (augmentation de la pile d'appels). Donc, dans les applications pratiques, il n’est pas nécessaire de disposer d’une mémoire illimitée (car tout est délimité de la même manière). Et la récurrence a souvent besoin de plus de mémoire que d'itération.
Agent_L
@Agent_L Oui, la récursivité nécessite une mémoire non limitée pour stocker toutes les trames de la pile. Avec une approche de récursivité, la mémoire non limitée est requise, mais elle n'est pas séparable intuitivement du séquencement des opérations, contrairement aux itérations.
Gilles, arrête d'être méchant
1
La thèse de Church-Turing pourrait être intéressante. Les machines de Turing sont des machines hautement itératives sans concept de récurrence (inhérent). Le lambda calcul est un langage conçu pour exprimer les calculs de manière récursive. La thèse de Church-Turing a montré que toutes les expressions lambda pouvaient être évaluées sur une machine de Turing, reliant récursivité et itération.
Cort Ammon
1
@BlackVegetable Si une méthode récursive n'a pas de variables internes et que la seule mémoire utilisée est la pile d'appels (ce qui peut être optimisé par TCO), sa version itérative n'aura probablement pas non plus de variables internes et utilisera uniquement une quantité de mémoire constante ( variables) partagées sur toutes les itérations, comme compteur.
Agent_L
33

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.

Yuval Filmus
la source
25

a(n,m)

s

push(s,x)xxpop(s)empty(s)

Ackermann(n0,m0):

  • s= (initialise la pile vide)
  • push(s,n0)
  • push(s,m0)
  • while(true):
    • mpop(s)
    • if(empty(s)):
      • return m (cela termine la boucle)
    • npop(s)
    • if(n=0):
      • push(s,m+1)
    • else if(m=0):
      • push(s,n1)
      • push(s,1)
    • else:
      • push(s,n1)
      • push(s,n)
      • push(s,m1)

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.

Paŭlo Ebermann
la source
16
Je pense que c'est un point important. Vous avez montré de manière explicite que la récursivité n’a rien de spécial et qu’elle peut être supprimée simplement en gardant une trace de la pile d’appels vous-même, au lieu de laisser le compilateur le faire. La récursivité est juste une fonctionnalité du compilateur qui facilite l'écriture de ce type de programme.
David Richerby
4
Merci d'avoir pris l'effort d'écrire le programme demandé.
Tobi Alafin
16

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?

Alexander - Rétablir Monica
la source
2

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.

Louis Giokas
la source