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 pile explicite. Chaque récursion peut-elle être transformée en itération?
L'exemple (compteur?) Dans le post 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))
Vous pouvez toujours transformer une fonction récursive dans un processus itératif? Oui, absolument, et la thèse de Church-Turing, il prouve si ma mémoire est bonne. En termes simples, il affirme que ce qui est calculable par une fonction récursive est calculable par un modèle itératif (comme la machine de Turing) et vice-versa. La thèse n'est pas de vous dire précisément comment faire la conversion, mais il ne dit que c'est certainement possible.
Dans de nombreux cas, la conversion d'une fonction récursive, c'est facile. Knuth propose plusieurs techniques dans "The Art of Computer Programming". Et souvent, une chose calculées récursivement peut être calculée par une approche totalement différente en moins de temps et d'espace. L'exemple le plus classique est la suite de Fibonacci ou des séquences de celle-ci. Vous avez sûrement rencontré ce problème dans votre degré de plan.
Sur le revers de cette pièce, on peut certainement imaginer un système de programmation tellement avancé que pour traiter une définition récursive d'une formule comme une invitation à memoize avant les résultats, offrant ainsi la vitesse d'avantages sans les tracas de dire à l'ordinateur exactement les étapes à suivre dans le calcul d'une formule avec une définition récursive. Dijkstra presque certainement imaginer un tel système. Il a passé un long moment à essayer de séparer la mise en œuvre de la sémantique d'un langage de programmation. Puis de nouveau, sa non-déterministe et le multitraitement de langages de programmation sont dans une ligue au-dessus de la pratique de programmeur professionnel.
En dernière analyse, de nombreuses fonctions sont tout simplement plus facile à comprendre, lire et écrire en forme récursive. Sauf si il y a une raison impérative, vous ne devriez probablement pas (manuellement) la conversion de ces fonctions à une explicitement algorithme itératif. Votre ordinateur va gérer ce travail correctement.
Je peux voir une raison impérieuse. Supposons que vous avez un prototype de système dans un super-langage de haut niveau comme [l'enfilage de l'amiante sous-vêtements] Scheme, Lisp, Haskell, OCaml, Perl, ou Pascal. Supposons que les conditions sont telles que vous avez besoin d'une mise en œuvre en C ou en Java. (Peut-être que c'est de la politique.) Ensuite, vous pouvez certainement avoir quelques fonctions écrites de manière récursive, mais qui, traduit littéralement, allait exploser votre système d'exécution. Par exemple, l'infini de la queue de la récursivité est possible dans le Schéma, mais le même langage provoque un problème pour les C environnements. Un autre exemple est l'utilisation de lexicalement fonctions imbriquées et statique de la portée, Pascal prend en charge, mais C n'est pas.
Dans ces circonstances, vous pouvez essayer de surmonter la résistance politique à la langue d'origine. Vous pourriez trouver vous-même de réimplanter Lisp mal, comme dans Greenspun (langue-dans-joue) dixième de la loi. Ou vous pourriez juste trouver une approche complètement différente de la solution. Mais dans tous les cas, il y a sûrement un moyen.
Est-il toujours possible d'écrire un non-récursive pour chaque fonction récursive?
Oui. Une simple preuve formelle est de montrer que les deux µ récursivité et un non-récursive de calcul tels que les GOTO sont à la fois Turing. Depuis tous les Turing calculs sont strictement équivalentes en leur puissance expressive, toutes les fonctions récursives peuvent être mises en œuvre par le non-récursive de Turing-complet de calcul.
Malheureusement, je suis incapable de trouver une bonne définition officielle de GOTO en ligne voici une:
Un GOTO programme est une séquence de commandes P exécuté sur un registre de la machine tels que P est l'un des suivants:
HALT, ce qui interrompt l'exécutionroù=est un registreroù+ 1est un registreroùrest une étiquette=oùrest tout registre et– 1est une étiquette- Un label, suivi par l'une des commandes ci-dessus.
Cependant, les conversions entre récursives et non récursives fonctions n'est pas toujours trivial (sauf par mindless manuel de la ré-implémentation de la pile d'appel).
Récursivité est implémentée comme des cheminées ou des constructions similaires dans les interprètes réelles ou les compilateurs. Alors vous pouvez certainement convertir une fonction récursive d’un homologue itérative parce que c’est comment il se fait toujours (si automatiquement). Vous allez juste être duplication de travail du compilateur dans une ad-hoc et probablement de façon très laide et inefficace.
En principe oui, en substance, ce que vous finissez par avoir à faire est de remplacer les appels de méthode (ce qui implicitement pousser de l'état sur la pile) en explicite de la pile pousse à se rappeler où l '"appel" avait obtenu jusqu'à, puis d'exécuter la "méthode appelée" à la place.
J'imagine que la combinaison d'une boucle, d'une pile et d'une machine d'état peut être utilisé pour tous les scénarios par gros simulant les appels de méthode. Si oui ou non cela va être "mieux" (soit plus rapide ou plus efficace dans un certain sens) n'est pas vraiment possible de dire en général.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
