Question

reddit enfilez élevé une question apparemment intéressante:

  

Queue fonctions récursives peuvent trivialement être converties en fonctions itératives. D'autres, peuvent être transformés en utilisant une pile explicite. Can tous récursion être transformé en itération?

Le (? Compteur) par exemple dans le poste 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))
Était-ce utile?

La solution

Pouvez-vous tourner toujours une fonction récursive dans un processus itératif? Oui, absolument, et la thèse Church-Turing prouve, si ma mémoire est bonne. En ce qui concerne laïcs, il précise que ce qui est calculable par des fonctions récursives est calculable par un modèle itératif (comme la machine de Turing) et vice-versa. La thèse ne précise pas vous dire comment faire la conversion, mais il ne dit qu'il est certainement 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 récursive peut être calculée par une approche complètement différente en moins de temps et de l'espace. L'exemple classique est celui des nombres de Fibonacci ou des séquences de ceux-ci. Vous avez sûrement rencontré ce problème dans votre plan de degré.

Sur le revers de la médaille, nous pouvons certainement imaginer un système de programmation si avancée que pour traiter une définition récursive d'une formule comme une invitation à memoize résultats antérieurs, offrant ainsi le gain de vitesse sans les tracas de dire l'ordinateur exactement lequel les étapes à suivre dans le calcul d'une formule avec une définition récursive. Dijkstra presque certainement pas imaginer un tel système. Il a passé beaucoup de temps à essayer de séparer la mise en œuvre de la sémantique d'un langage de programmation. Là encore, ses langages de programmation non déterministe et multitraitement sont dans une ligue au-dessus du pratiquant programmeur professionnel.

Dans l'analyse finale, de nombreuses fonctions sont tout simplement plus facile simple à comprendre, lire et écrire sous forme récursive. À moins qu'il ya une raison impérieuse, vous devriez probablement pas (manuellement) convertir ces fonctions à un algorithme explicitement itérative. Votre ordinateur gérer correctement ce travail.

Je vois une raison impérieuse. Supposons que vous avez un système prototype dans une langue de niveau super élevé comme [ sous-vêtements de l'amiante enfiler ] Scheme, Lisp, Haskell, OCaml, Perl ou Pascal. conditions Supposons sont telles que vous avez besoin d'une implémentation en C ou Java. (Peut-être est politique.) Ensuite, vous pourriez certainement avoir des fonctions écrites récursive mais qui, traduit littéralement, exploserait votre système d'exécution. Par exemple, la queue infinie récursion est possible dans le schéma, mais le même langage pose un problème pour les environnements existants C. Un autre exemple est l'utilisation de fonctions imbriquées lexicalement et la portée statique, ce qui soutient Pascal, mais C ne fonctionne pas.

Dans ces circonstances, vous pourriez essayer de surmonter la résistance politique à la langue d'origine. Vous pourriez vous retrouver réimplémentant Lisp mal, comme en droit dixième de (la langue dans la joue) Greenspun. Ou vous pourriez trouver une approche complètement différente de solution. Mais en tout état de cause, il y a sûrement une façon.

Autres conseils

  

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

Oui. Une simple preuve formelle est de montrer que les deux μ récursion et non calcul récursif tels que GOTO sont à la fois complète Turing. Étant donné que tous complets lithiase sont strictement équivalents Turing en leur pouvoir expressif, par le calcul complet de Turing-non-récursive peut être mis en œuvre toutes les fonctions récursives.

Malheureusement, je suis incapable de trouver une bonne définition formelle de GOTO en ligne alors voici une:

Un programme GOTO est une séquence de commandes P exécuté sur un machine à registre tel que P est l'un des suivants:

  • HALT, qui interrompt l'exécution
  • r = r + 1r est un registre
  • r = r – 1r est un registre
  • GOTO xx est un label
  • IF r ≠ 0 GOTO xr est un registre et x est un label
  • Une étiquette, suivie par l'une des commandes ci-dessus.

Cependant, les conversions entre les fonctions récursives et non récursives ne sont pas toujours trivial (sauf par réimplantation manuelle sans esprit de la pile d'appel).

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

récursion est mis en œuvre comme des piles ou des constructions similaires dans les interprètes réels ou des compilateurs. Donc, vous pouvez certainement convertir une fonction récursive à un homologue itérative parce que c'est la façon dont il a toujours fait (si automatiquement) . Vous aurez juste dupliquer le travail de compilateur dans un réseau ad-hoc et probablement d'une manière très laid et inefficace.

En gros oui, en substance ce que vous finissez par avoir à faire est de remplacer les appels de méthode (qui poussent implicitement état sur la pile) dans une pile explicite pousse à se rappeler où le « appel précédent » avait obtenu jusqu'à, puis exécutez le ' méthode dite » à la place.

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

  • flot d'exécution de la fonction récursive peut être représentée comme un arbre.

  • Le même raisonnement peut être fait par une boucle, qui utilise une structure de données pour traverser cet arbre.

  • profondeur d'abord traversée peut être fait en utilisant une pile, parcours en largeur peut être fait en utilisant une file d'attente.

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

.
  

Peut-récursion se faire en une seule boucle? Oui, parce que

     

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

     
      
  1. chercher une instruction,
  2.   
  3. évaluer,
  4.   
  5. goto 1.
  6.   

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

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

En principe, il est toujours possible de retirer récursivité et le remplacer par itération dans une langue qui a un état infini tant pour les structures de données et pour la pile d'appel. Ceci est une conséquence fondamentale de la Thèse de Church.

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

récursion Parfois, le remplacement est beaucoup plus facile que cela. Récursivité utilisé pour être la chose à la mode enseigné dans CS dans les années 1990, et donc beaucoup de développeurs moyen de ce moment-là pensé que si vous avez résolu quelque chose avec récursion, il était une meilleure solution. Alors, ils utiliseraient récursion au lieu de boucle arrière pour inverser l'ordre, ou des choses stupides comme ça. Alors parfois enlever récursion est un simple « bah, ça était évident » type d'exercice.

Ceci est moins un problème maintenant, comme la mode a évolué vers d'autres technologies.

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

récursion La suppression est un problème complexe et qui est faisable dans des circonstances bien définies.

Les cas ci-dessous sont parmi les facilement:

Appart de la pile explicite, un autre motif pour convertir récursion en itération est avec l'utilisation d'un trampoline.

Ici, les fonctions soit renvoient le résultat final, ou une fermeture de l'appel de la fonction qu'il aurait autrement effectué. Ensuite, la fonction de déclenchement (trampolining) garder invoquant les fermetures retour 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 queue.

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

Je dirais que oui - un appel de fonction est rien, mais une goto et une opération de pile (en gros). Tout ce que vous devez faire est d'imiter la pile qui est construit en invoquant des fonctions et faire quelque chose de similaire en tant que goto (vous pouvez imiter GOTO avec des langues qui ne sont pas explicitement ce mot-clé trop).

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

Suit un paragraphe qui peut vous donner une indication sur l'endroit où commencer:

  

Résolution d'une relation de récurrence signifie l'obtention d'un solution de forme fermée : un non fonction récursive de n.

Voir aussi le dernier paragraphe de cette entrée.

  

Il est possible de convertir tout algorithme récursif à un non récurrent   un, mais souvent la logique est beaucoup plus complexe et exige de faire   l'utilisation d'une pile. En fait, la récursivité lui-même utilise une pile: la   pile de la fonction.

Plus de détails: https://developer.mozilla.org / fr-fr / docs / Web / JavaScript / Guide / Fonctions

tazzego, récursivité signifie qu'une fonction lui-même appeler si vous le vouliez ou non. Quand les gens parlent si oui ou non les choses peuvent se faire sans récursion, ils veulent dire cela 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.

Avec cela à l'esprit, à peu près tout ce que vous dites est un non-sens. La seule autre chose que vous dites ce n'est pas un non-sens est l'idée que vous ne pouvez pas imaginer la programmation sans callstack. C'est quelque chose qui avait été fait pendant des décennies jusqu'à l'aide d'un callstack est devenu populaire. Les anciennes versions de FORTRAN ne disposaient pas d'un callstack et ils travaillaient très bien.

Par ailleurs, il existe des langages de Turing-complet qui mettent en oeuvre uniquement récursivité (par exemple SML) comme un moyen de bouclage. Il existe également des langues Turing-complet qui ne mettent en œuvre itération comme un moyen de boucle (par exemple FORTRAN IV). La thèse Church-Turing prouve que tout est possible dans une des langues de récursivité ne peut se faire dans une langue non récurrente et Vica versa par le fait qu'ils ont tous deux la propriété de Turing complet.

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
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top