Éliminer la récursivité - un aperçu de la théorie dans les coulisses

Je suis nouveau sur ce site et cette question n'est certainement pas au niveau de la recherche - mais bon. J'ai un peu d'expérience en génie logiciel et presque aucun en CSTheory, mais je le trouve attrayant. Pour faire une longue histoire, je voudrais une réponse plus détaillée à ce qui suit si cette question est acceptable sur ce site.

Donc, je sais que chaque programme récursif a un analogue itératif et je comprends en quelque sorte l'explication populaire qui lui est proposée en conservant quelque chose de similaire à la "pile système" et en poussant les paramètres d'environnement comme l'adresse de retour, etc. Je trouve ce type d'ondes manuelles .

Étant un peu plus concret, je voudrais (formellement) voir comment prouver cette affirmation dans les cas où vous avez une fonction invoquant la chaîne . De plus, que se passe-t-il s'il y a des instructions conditionnelles qui pourraient amener un appeler un certain ? C'est-à-dire que le graphe d'appel de fonction potentiel a des composants fortement connectés.F i F $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$$F_i$$F_j$

Je voudrais savoir comment ces situations peuvent être gérées par disons un convertisseur récursif en itératif. Et la description ondulée à laquelle j'ai fait référence plus haut est-elle vraiment suffisante pour ce problème? Je veux dire alors pourquoi est-ce que je trouve la suppression de la récursivité dans certains cas facile. En particulier, supprimer la récursivité de la traversée en pré-commande d'un arbre binaire est vraiment facile - c'est une question d'entretien standard, mais supprimer la récursivité en cas de post-commande a toujours été un cauchemar pour moi.

Ce que je demande vraiment, c'est questions$2$

(1) Existe-t-il vraiment une preuve plus formelle (convaincante?) Que la récursivité peut être convertie en itération?

(2) Si cette théorie est vraiment là-bas, alors pourquoi est-ce que je trouve, par exemple, l' itération de la précommande plus facile et la post-commande si difficile? (autre que mon intelligence limitée)

Si je comprends bien, vous êtes clair sur la conversion de fonctions qui ne contiennent aucun autre appel de fonction que pour elles-mêmes.

Donc , supposons que nous avons une « chaîne d'appel » . Si nous supposons en outre que ne sont pas eux-mêmes récursifs (car nous les avons déjà convertis), nous pouvons intégrer tous ces appels dans la définition de qui devient ainsi une fonction directement récursive que nous pouvons déjà traiter.$F \to F_1 \to \dots \to F_n \to F$$F_1, \dots, F_n$$F$

Cela échoue si certains ont lui-même une chaîne d'appel récursive dans laquelle se produit, c'est-à-dire . Dans ce cas, nous avons une récursion mutuelle qui nécessite une autre astuce pour se débarrasser. L'idée est de calculer les deux fonctions simultanément. Par exemple, dans le cas trivial: F F j → ⋯ → F → ⋯ → F $F_j$$F$$F_j \to \dots \to F \to \dots \to F_j$

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

avec f'et les g'fonctions non-récursifs (ou au moins indépendant de fet g) devient

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

Cela s'étend naturellement à plus de fonctions impliquées et à des fonctions plus compliquées.

Oui, il existe des raisons convaincantes de croire que la récursivité peut être transformée en itération. C'est ce que fait chaque compilateur lorsqu'il traduit le code source en langage machine. Pour la théorie, vous devez suivre les suggestions de Dave Clarke. Si vous souhaitez voir le code réel qui convertit la récursivité en code non récursif, jetez un œil au machine.mllangage MiniML dans mon zoo PL (notez que la loopfonction en bas, qui exécute réellement le code, est récursive et donc elle peut être trivialement converti en une boucle réelle).

Encore une chose. MiniML ne prend pas en charge les fonctions mutuellement récursives. Mais ce n'est pas un problème. Si vous avez une récursion mutuelle entre les fonctions

la récursivité peut être exprimée en termes d'une seule carte récursive

Vous voudrez peut-être regarder la machine SECD . Un langage fonctionnel (bien qu'il puisse s'agir de n'importe quel langage) est traduit en une série d'instructions qui gèrent des choses comme mettre des arguments de piles, "invoquer" de nouvelles fonctions et ainsi de suite, le tout géré par une simple boucle.
Les appels récursifs ne sont jamais réellement invoqués. Au lieu de cela, les instructions du corps de la fonction appelée sont placées sur la pile pour s'exécuter.

Une approche connexe est la machine CEK .

Ces deux éléments existent depuis longtemps, il y a donc beaucoup de travail là-dessus. Et bien sûr, il existe des preuves qu'ils fonctionnent et la procédure de "compilation" d'un programme en instructions SECD est linéaire dans la taille du programme (il n'a pas à penser au programme).

Le point de ma réponse est qu'il existe une procédure automatique pour faire ce que vous voulez. Malheureusement, la transformation ne sera pas nécessairement en termes de choses qui sont immédiatement faciles à interpréter pour un programmeur. Je pense que la clé est que lorsque vous voulez itérer un programme, vous devez stocker sur la pile ce que le programme doit faire lorsque vous revenez d'un appel de fonction itéré (c'est ce qu'on appelle une continuation). Pour certaines fonctions (telles que les fonctions récursives de queue), la continuation est triviale. Pour d'autres, la suite peut être très complexe, surtout si vous devez l'encoder vous-même.

Q : "Existe-t-il vraiment une preuve plus formelle (convaincante?) Que la récursivité peut être convertie en itération?"

R : L'intégralité de Turing d'une machine de Turing :-)

À part les blagues, le modèle de machine à programme stocké à accès aléatoire (RASP) équivalent de Turing est proche du fonctionnement des microprocesseurs réels et son jeu d'instructions ne contient qu'un saut conditionnel (pas de récursivité). La possibilité d'auto-modification dinamique du code facilite la mise en œuvre des sous-programmes et des appels récursifs.

Je pense que vous pouvez trouver de nombreux articles / articles sur la " conversion récursive en itérative " (voir la réponse de Dave ou simplement Google les mots-clés), mais peut-être une approche moins connue (et pratique ) est la dernière recherche sur la mise en œuvre matérielle d'algorithmes récursifs ( utilisant le langage VHDL qui est "compilé" directement dans un morceau de matériel). Par exemple, voir l'article de V.Sklyarov "Implémentation basée sur FPGA d'algorithmes récursifs " ( L'article suggère une nouvelle méthode pour implémenter des algorithmes récursifs dans le matériel. .... Deux applications pratiques des algorithmes récursifs dans le domaine du tri et de la compression des données ont été étudiées en détail .... ).

Si vous êtes familier avec les langages qui prennent en charge les lambdas, une solution consiste à étudier la transformation CPS. Supprimer l'utilisation de la pile d'appels (et la récursivité en particulier) est exactement ce que fait la transformation CPS. Il transforme un programme contenant des appels de procédure en un programme avec uniquement des appels de queue (vous pouvez les considérer comme des gotos, qui est une construction itérative).

La transformation CPS est étroitement liée à la conservation explicite d'une pile d'appels dans une pile traditionnelle basée sur un tableau, mais au lieu d'un tableau, la pile d'appels est représentée avec des fermetures liées.

à mon avis, cette question remonte aux origines mêmes des définitions du calcul et a longtemps été rigoureusement prouvée à cette époque où le calcul lambda de l'église (qui capture très bien le concept de récursivité) s'est avéré être équivalent aux machines de Turing et est contenu dans la terminologie encore utilisée "langues / fonctions récursives". également apparemment une référence clé ultérieure le long de ces lignes est la suivante

Comme l'a souligné l'article de 1965 de Peter Landin, A Correspondance between ALGOL 60 and Church's Lambda-notation, les langages de programmation procédurale séquentielle peuvent être compris en termes de calcul lambda, qui fournit les mécanismes de base pour l'abstraction procédurale et l'application de la procédure (sous-programme).

une grande partie du bkd à ce sujet se trouve dans cette page wikipedia thèse église-turing . Je ne suis pas sûr des détails exacts, mais l'article de Wikipédia semble indiquer que c'est Rosser (1939) qui a le premier prouvé cette équivalence entre le calcul lambda et les machines de turing. peut-être / vraisemblablement que son papier a un mécanisme semblable à une pile pour convertir les appels lambda (éventuellement récursifs) en construction tm?

Rosser, JB (1939). "Une Exposition Informelle de Preuves du Théorème de Godel et du Théorème de l'Église". The Journal of Symbolic Logic (The Journal of Symbolic Logic, Vol. 4, No. 2) 4 (2): 53–60. doi: 10.2307 / 2269059. JSTOR 2269059.

notez bien sûr pour toute personne intéressée par les principes que le langage Lisp moderne et la variante Scheme ont intentionnellement une forte ressemblance avec le lambda calcul. l'étude du code d'interprète pour l'évaluation de l'expression mène à des idées qui étaient à l'origine contenues dans des articles pour l'intégralité du turing du calcul lambda.