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

Un fil rouge a soulevé une question apparemment intéressante:

Les fonctions récursives de la queue peuvent être converties en fonctions itératives. D’autres peuvent être transformés en utilisant une stack explicite. Chaque récursion peut-elle être transformée en itération?

L’exemple (compteur?) Dans le post est la paire:

(define (num-ways xy) (case ((= x 0) 1) ((= y 0) 1) (num-ways2 xy) )) (define (num-ways2 xy) (+ (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 indique que ce qui est calculable par les 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 définitivement possible.

Dans de nombreux cas, la conversion d’une fonction récursive est facile. Knuth propose plusieurs techniques dans “The Art of Computer Programming”. Et souvent, une chose calculée de manière récursive 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 de diplôme.

D’un autre côté de la pièce, on peut certainement imaginer un système de programmation si avancé qu’il considère une définition récursive d’une formule comme une invitation à mémoriser les résultats antérieurs, offrant ainsi l’avantage de la vitesse sans avoir à indiquer à l’ordinateur exactement les é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é beaucoup de temps à 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 au-dessus du programmeur professionnel.

En dernière parsing, de nombreuses fonctions sont simplement plus faciles à comprendre, à lire et à écrire sous forme récursive. À moins d’une raison impérieuse, vous ne devriez probablement pas (manuellement) convertir ces fonctions en un algorithme explicitement itératif. Votre ordinateur va gérer ce travail correctement.

Je peux voir une raison convaincante. Supposons que vous ayez un prototype de système dans un langage de très haut niveau, comme Scheme, Lisp, Haskell, OCaml, Perl ou Pascal. Supposons que les conditions soient telles que vous ayez besoin d’une implémentation en C ou en Java. (Peut-être que c’est 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écursion de la queue infinie 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 lexiquement nestedes et de scopes statiques, 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 Lisp, comme dans la dixième loi de Greenspun. Ou vous pourriez simplement trouver une approche complètement différente de la solution. Mais de toute façon, 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 les deux récursions et les calculs non récursifs tels que GOTO sont tous deux Turing complets. Puisque tous les calculs complets de Turing sont ssortingctement équivalents dans leur puissance expressive, toutes les fonctions récursives peuvent être implémentées par le calcul Turing-complet non récursif.

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

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

  • HALT , qui arrête l’exécution
  • r = r + 1r est un registre
  • r = r – 1r est un registre
  • GOTO xx est une étiquette
  • IF r ≠ 0 GOTO xr est un registre et x est une étiquette
  • Une étiquette, suivie de l’une des commandes ci-dessus.

Cependant, les conversions entre fonctions récursives et non récursives ne sont pas toujours sortingviales (sauf par une ré-implémentation manuelle inconsidérée de la stack d’appels).

La récursivité est implémentée sous forme de stacks 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 cela se fait toujours (si automatiquement) . Vous ne ferez que dupliquer le travail du compilateur de manière ad hoc et probablement d’une manière très laide et inefficace.

Essentiellement, oui, ce que vous finissez par faire est de remplacer les appels de méthode (qui implicitement poussent l’état sur la stack) dans des poussées de stack explicites pour se rappeler où l’appel précédent s’est déroulé, puis d’exécuter la méthode appelée. au lieu.

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

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

  • Le stream d’exécution de la fonction récursive peut être représenté sous la forme d’un arbre.

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

  • La traversée en profondeur peut être effectuée en utilisant une stack, la traversée en largeur peut être effectuée en utilisant une queue.

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

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

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

  1. chercher une instruction,
  2. évaluez-le,
  3. aller à 1.

Oui, il est toujours possible d’écrire une version non récursive. La solution sortingviale consiste à utiliser une structure de données de stack 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 stack d’appels. Ceci 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 dans lequel la quantité de mémoire pouvant être allouée dans le programme est limitée mais où la quantité de stack d’appel pouvant être utilisée est illimitée (C 32 bits où l’adresse des variables de la stack n’est pas accessible). Dans ce cas, la récursivité est plus puissante simplement parce qu’elle peut utiliser plus de mémoire; il n’y a pas assez de mémoire explicitement allouable pour émuler la stack d’appels. Pour une discussion détaillée à ce sujet, voir cette discussion .

Parfois, remplacer 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 de nombreux développeurs de l’é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 revenir en arrière pour inverser l’ordre ou des choses idiotes comme ça. Donc, parfois, supprimer la récursivité est un type d’exercice simple, qui était évident.

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

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

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

Les cas ci-dessous sont parmi les plus faciles:

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

Mis à part la stack explicite, un autre modèle de conversion de 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’il aurait autrement effectué. Ensuite, la fonction d’initiation (trampoline) continue à appeler les fermetures renvoyées jusqu’à ce que le résultat final soit atteint.

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

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

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

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

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

Suit un paragraphe qui peut vous donner une idée de l’endroit où commencer:

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

Regardez aussi le dernier paragraphe de cette entrée .

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

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

tazzego, la récursion signifie qu’une fonction s’appellera elle-même que cela vous plaise ou non. Lorsque les gens parlent de savoir si les choses peuvent être faites sans récursivité, elles le font et vous ne pouvez pas dire «non, ce n’est pas vrai, car je ne suis pas d’accord avec la définition de la récursivité».

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

Au fait, il existe des langages Turing-complete qui implémentent uniquement la récursivité (par exemple SML) comme moyen de bouclage. Il existe également des langages Turing-complete qui implémentent uniquement l’itération comme moyen de bouclage (par exemple, FORTRAN IV). La thèse de Church-Turing prouve que tout ce qui est possible dans les langages uniquement récursifs peut être fait dans un langage non récursif et vice-versa du fait qu’ils ont tous deux la propriété de turing-complete.

Voici un algorithme itératif:

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

Une question: si en premier lieu la fonction fait une copie d’elle-même dans un espace mémoire vide aléatoire, et puis au lieu de s’appeler elle-même appeler la copie, est-ce toujours une récursivité? (1) Je dirais oui.

L’utilisation explicite de la stack est-elle un moyen réel de supprimer la récursivité? (2) Je dirais non. Fondamentalement, n’imitons-nous pas ce qui se passe lorsque nous utilisons explicitement la récursivité? Je pense que nous ne pouvons pas définir la récursivité simplement comme “une fonction qui s’appelle elle-même”, car je vois aussi la récursivité dans le “code de copie” (1) et dans “l’utilisation explicite de la stack” (2).

De plus, je ne vois pas comment le scanner démontre que tous les algorithmes récursifs peuvent devenir itératifs. Il me semble seulement que “tout” ayant le “pouvoir” de la machine Turing peut exprimer tous les algorithmes que cela peut exprimer. Si Turing-machine ne peut pas récurer, nous sums sûrs que tous les algo récursifs ont leur traduction inter-active … La machine-Turing peut-elle être récursive? Selon moi, si cela peut être “implémenté” (par n’importe quel moyen), alors nous pouvons dire qu’il l’a. A-t-il? Je ne sais pas.

Tous les vrais processeurs que je connais peuvent récurer. Honnêtement, je ne vois pas comment programmer pour de vrai sans avoir une stack d’appels, et je pense que c’est ce qui rend la récursivité possible en premier.

En évitant la copie (1) et la “stack imitée” (2), avons-nous démontré que tout algo récursif peut être, sur des machines réelles, exprimé de manière itérative?! Je ne peux pas voir où nous l’avons démontré.