Chaque récursion peut-elle être convertie en itération?

Un fil de discussion reddit a soulevé une question apparemment intéressante:

Les fonctions récursives de queue peuvent être converties de manière simple en fonctions itératives. D'autres peuvent être transformés en utilisant une pile explicite. Peut chaque récursion se transformer en itération?

L'exemple (compteur?) Dans l'article est la paire:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Pouvez-vous toujours transformer une fonction récursive en une fonction itérative? Oui, absolument, et la thèse de Church-Turing le prouve si la mémoire est bonne. En termes simples, il déclare que ce qui est calculable par des fonctions récursives est calculable par un modèle itératif (tel que la machine de Turing) et vice versa. La thèse ne vous dit pas précisément comment faire la conversion, mais elle dit que c'est certainement possible.

Dans de nombreux cas, la conversion d'une fonction récursive est facile. Knuth propose plusieurs techniques dans "L'art de la programmation informatique". Et souvent, une chose calculée récursivement peut être calculée par une approche complètement différente en moins de temps et d'espace. L'exemple classique de ceci est les nombres de Fibonacci ou leurs séquences. Vous avez sûrement rencontré ce problème dans votre plan d'études.

De l'autre côté de cette médaille, on peut certainement imaginer un système de programmation suffisamment avancé pour traiter une définition récursive d'une formule comme une invitation à mémoriser des résultats antérieurs, offrant ainsi l'avantage de la vitesse sans avoir à dire à l'ordinateur exactement quelles étapes à suivre suivre dans le calcul d'une formule avec une définition récursive. Dijkstra a presque certainement imaginé un tel système. Il a passé un long moment à essayer de séparer l'implémentation de la sémantique d'un langage de programmation. Là encore, ses langages de programmation non déterministes et multiprocesseurs sont dans une ligue au-dessus du programmeur professionnel en exercice.

En dernière analyse, de nombreuses fonctions sont tout simplement plus faciles à comprendre, à lire et à écrire sous forme récursive. À moins qu'il n'y ait une raison impérieuse, vous ne devriez probablement pas (manuellement) convertir ces fonctions en un algorithme explicitement itératif. Votre ordinateur gérera ce travail correctement.

Je peux voir une raison convaincante. Supposons que vous ayez un système prototype dans un langage de très haut niveau comme [ enfiler des sous-vêtements en amiante ] Scheme, Lisp, Haskell, OCaml, Perl ou Pascal. Supposons que les conditions soient telles que vous ayez besoin d'une implémentation en C ou Java. (C'est peut-être de la politique.) Alors vous pourriez certainement avoir des fonctions écrites récursivement mais qui, traduites littéralement, feraient exploser votre système d'exécution. Par exemple, la récursivité infinie de la queue est possible dans Scheme, mais le même idiome pose un problème pour les environnements C existants. Un autre exemple est l'utilisation de fonctions imbriquées lexicalement et de portée statique, que Pascal prend en charge mais pas C.

Dans ces circonstances, vous pourriez essayer de surmonter la résistance politique à la langue d'origine. Vous pourriez vous retrouver à réimplémenter mal Lisp, comme dans la dixième loi de Greenspun (ironique). Ou vous pourriez simplement trouver une approche complètement différente de la solution. Mais en tout cas, il y a sûrement un moyen.

Est-il toujours possible d'écrire une forme non récursive pour chaque fonction récursive?

Oui. Une preuve formelle simple est de montrer que la récursion µ et un calcul non récursif tel que GOTO sont tous deux complets de Turing. Puisque tous les calculs complets de Turing sont strictement équivalents dans leur pouvoir expressif, toutes les fonctions récursives peuvent être implémentées par le calcul non récursif de Turing-complet.

Malheureusement, je ne parviens pas à trouver une bonne définition formelle de GOTO en ligne, alors en voici une:

Un programme GOTO est une séquence de commandes P exécutées sur une machine de registre telle que P est l'une des suivantes:

• HALT, qui arrête l'exécution
• r = r + 1où rest un registre
• r = r – 1où rest un registre
• GOTO xoù xest une étiquette
• IF r ≠ 0 GOTO xoù rest un registre et xest une étiquette
• Une étiquette, suivie de l'une des commandes ci-dessus.

Cependant, les conversions entre les fonctions récursives et non récursives ne sont pas toujours triviales (sauf par une ré-implémentation manuelle insensée de la pile d'appels).

Pour plus d'informations, consultez cette réponse .

La récursivité est implémentée sous forme de piles ou de constructions similaires dans les interpréteurs ou compilateurs réels. Vous pouvez donc certainement convertir une fonction récursive en une contrepartie itérative, car c'est toujours comme cela que cela se fait (si automatiquement) . Vous allez simplement dupliquer le travail du compilateur de manière ad hoc et probablement d'une manière très moche et inefficace.

Fondamentalement, oui, ce que vous finissez par avoir à faire est de remplacer les appels de méthode (qui poussent implicitement l'état sur la pile) dans des poussées de pile explicites pour se souvenir où `` l'appel précédent '' était arrivé, puis d'exécuter la `` méthode appelée '' au lieu.

J'imagine que la combinaison d'une boucle, d'une pile et d'une machine à états pourrait être utilisée pour tous les scénarios en simulant essentiellement les appels de méthode. Il n'est pas vraiment possible de dire si cela va être «meilleur» (soit plus rapide, soit plus efficace dans un certain sens) en général.

• Le flux d'exécution de fonction récursive peut être représenté sous forme d'arborescence.

• La même logique peut être réalisée par une boucle, qui utilise une structure de données pour traverser cet arbre.

• La traversée en profondeur peut être effectuée à l'aide d'une pile, la traversée en largeur peut être effectuée à l'aide d'une file d'attente.

Donc, la réponse est oui. Pourquoi: https://stackoverflow.com/a/531721/2128327 .

Une récursion peut-elle être effectuée en une seule boucle? Oui parce que

une machine de Turing fait tout ce qu'elle fait en exécutant une seule boucle:

1. chercher une instruction,
2. l'évaluer,
3. aller à 1.

Oui, en utilisant explicitement une pile (mais la récursivité est beaucoup plus agréable à lire, à mon humble avis).

Oui, il est toujours possible d'écrire une version non récursive. La solution triviale consiste à utiliser une structure de données de pile et à simuler l'exécution récursive.

En principe, il est toujours possible de supprimer la récursivité et de la remplacer par une itération dans un langage qui a un état infini à la fois pour les structures de données et pour la pile d'appels. C'est une conséquence fondamentale de la thèse de Church-Turing.

Étant donné un langage de programmation réel, la réponse n'est pas aussi évidente. Le problème est qu'il est tout à fait possible d'avoir un langage où la quantité de mémoire pouvant être allouée dans le programme est limitée mais où la quantité de pile d'appels pouvant être utilisée est illimitée (C 32 bits où l'adresse des variables de pile n'est pas accessible). Dans ce cas, la récursivité est plus puissante simplement parce qu'elle a plus de mémoire qu'elle peut utiliser; il n'y a pas assez de mémoire explicitement allouable pour émuler la pile d'appels. Pour une discussion détaillée à ce sujet, consultez cette discussion .

Toutes les fonctions calculables peuvent être calculées par les machines de Turing et donc les systèmes récursifs et les machines de Turing (systèmes itératifs) sont équivalents.

Parfois, le remplacement de la récursivité est beaucoup plus facile que cela. La récursivité était la chose à la mode enseignée dans CS dans les années 1990, et donc beaucoup de développeurs moyens de cette époque pensaient que si vous résolviez quelque chose avec la récursivité, c'était une meilleure solution. Donc, ils utiliseraient la récursivité au lieu de faire une boucle en arrière pour inverser l'ordre, ou des choses idiotes comme ça. Donc, parfois, la suppression de la récursivité est un simple exercice de type «duh, c'était évident».

C'est moins un problème maintenant, car la mode s'est déplacée vers d'autres technologies.

La suppression de la récursivité est un problème complexe et est faisable dans des circonstances bien définies.

Les cas ci-dessous sont parmi les plus faciles:

• récursion de queue
• récursion linéaire directe

Outre la pile explicite, un autre modèle pour convertir la récursivité en itération est l'utilisation d'un trampoline.

Ici, les fonctions renvoient soit le résultat final, soit une fermeture de l'appel de fonction qu'elles auraient autrement effectué. Ensuite, la fonction d'initiation (trampoline) continue d'appeler les fermetures retournées jusqu'à ce que le résultat final soit atteint.

Cette approche fonctionne pour les fonctions mutuellement récursives, mais je crains que cela ne fonctionne que pour les appels de fin.

http://en.wikipedia.org/wiki/Trampoline_(computers)

Je dirais que oui - un appel de fonction n'est rien d'autre qu'un goto et une opération de pile (en gros). Tout ce que vous avez à faire est d'imiter la pile qui est construite en invoquant des fonctions et de faire quelque chose de similaire à goto (vous pouvez imiter gotos avec des langages qui n'ont pas explicitement ce mot-clé).

Jetez un œil aux entrées suivantes sur wikipedia, vous pouvez les utiliser comme point de départ pour trouver une réponse complète à votre question.

• Récursivité en informatique
• Relation réccurente

Suit un paragraphe qui peut vous indiquer par où commencer:

Résoudre une relation de récurrence signifie obtenir une solution de forme fermée : une fonction non récursive de n.

Jetez également un œil au dernier paragraphe de cette entrée .

Il est possible de convertir n'importe quel algorithme récursif en un algorithme non récursif, mais souvent la logique est beaucoup plus complexe et cela nécessite l'utilisation d'une pile. En fait, la récursivité elle-même utilise une pile: la pile de fonctions.

Plus de détails: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

tazzego, la récursivité signifie qu'une fonction s'appellera elle-même que vous le vouliez ou non. Quand les gens parlent de savoir si les choses peuvent ou non être faites sans récursivité, ils le pensent et vous ne pouvez pas dire "non, ce n'est pas vrai, parce que je ne suis pas d'accord avec la définition de la récursivité" comme une déclaration valide.

Dans cet esprit, à peu près tout ce que vous dites est absurde. La seule autre chose que vous dites qui n'est pas absurde est l'idée que vous ne pouvez pas imaginer la programmation sans pile d'appels. C'est quelque chose qui avait été fait pendant des décennies jusqu'à ce que l'utilisation d'une pile d'appels devienne populaire. Les anciennes versions de FORTRAN n'avaient pas de pile d'appels et elles fonctionnaient très bien.

À propos, il existe des langages complets de Turing qui n'implémentent que la récursivité (par exemple SML) comme moyen de bouclage. Il existe également des langages complets de Turing qui n'implémentent l'itération que comme moyen de bouclage (par exemple, FORTRAN IV). La thèse de Church-Turing prouve que tout ce qui est possible dans un langage uniquement récursif peut être fait dans un langage non récursif et vica-versa par le fait qu'ils ont tous deux la propriété de turing-complétude.

Voici un algorithme itératif:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end