J'ai utilisé beaucoup de récursivité sur mes nombreuses années de programmation pour résoudre des problèmes simples, mais je suis pleinement conscient que parfois vous avez besoin d'itération en raison de problèmes de mémoire / vitesse.
Donc, quelque part dans un passé très lointain, je suis allé essayer de trouver s'il existait un "modèle" ou un moyen manuel de transformer une approche récursive commune de l'itération et je n'ai rien trouvé. Ou du moins rien dont je me souvienne que cela aiderait.
- Existe-t-il des règles générales?
- Y a-t-il un "modèle"?
recursion
computer-science
theory
iteration
Gustavo Carreno
la source
la source
Réponses:
Habituellement, je remplace un algorithme récursif par un algorithme itératif en poussant les paramètres qui seraient normalement passés à la fonction récursive sur une pile. En fait, vous remplacez la pile de programmes par l'une des vôtres.
Remarque: si vous avez plus d'un appel récursif à l'intérieur et que vous souhaitez conserver l'ordre des appels, vous devez les ajouter dans l'ordre inverse à la pile:
doit être remplacé par
Edit: L'article Stacks and Recursion Elimination (ou le lien Article Backup ) donne plus de détails à ce sujet.
la source
(node)->()
par(node)->[actions]
où se trouve l'action() -> [actions]
. Ensuite, à l'extérieur, il vous suffit de sortir une action / continuation de la pile, de l'appliquer / l'exécuter, de pousser les actions qu'elle a renvoyées sur la pile dans l'ordre inverse et de répéter. Traversées contingentes / complexes, vous capturez simplement ce qui aurait été des variables de pile locales dans des pointeurs comptés par référence que vous fermez dans vos thunks, puis les thunks suivants peuvent dépendre des résultats des sous-traversées précédentes, etc.new
nous pouvons créer un objet sur le tas au lieu de la pile. Contrairement à la pile, le tas n'a pas de restrictions de mémoire. Voir gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.htmlVraiment, la façon la plus courante de le faire est de conserver votre propre pile. Voici une fonction de tri rapide récursif en C:
Voici comment nous pourrions le rendre itératif en conservant notre propre pile:
De toute évidence, cet exemple ne vérifie pas les limites de la pile ... et vous pouvez vraiment dimensionner la pile en fonction du pire des cas, compte tenu des valeurs gauche et droite. Mais vous avez l'idée.
la source
O(N) = O(R*L)
, oùL
est la somme de la complexité "pour la couche r", par exemple dans ce cas, vous avez duO(N)
travail à chaque étape pour faire les partitions, la profondeur récursive estO(R)
, c'est-à-dire le pire des casO(N)
, le cas moyenO(logN)
ici.Il semble que personne ne se soit demandé où la fonction récursive s'appelle plus d'une fois dans le corps et gère le retour à un point spécifique de la récursivité (c'est-à-dire non récursif-primitif). On dit que chaque récursivité peut être transformée en itération , il semble donc que cela devrait être possible.
Je viens de proposer un exemple C # de la façon de procéder. Supposons que vous ayez la fonction récursive suivante, qui agit comme une traversée de post-ordre, et que AbcTreeNode est un arbre à 3 aires avec des pointeurs a, b, c.
La solution itérative:
la source
Efforcez-vous de faire votre appel récursif Tail Recursion (récursion où la dernière instruction est l'appel récursif). Une fois que vous avez cela, le convertir en itération est généralement assez facile.
la source
Eh bien, en général, la récursivité peut être imitée comme une itération en utilisant simplement une variable de stockage. Notez que la récursivité et l'itération sont généralement équivalentes; l'un peut presque toujours être converti en l'autre. Une fonction récursive de queue est très facilement convertie en fonction itérative. Faites simplement de la variable accumulateur une variable locale et répétez au lieu de recurse. Voici un exemple en C ++ (C sans l'utilisation d'un argument par défaut):
Me connaissant, j'ai probablement fait une erreur dans le code, mais l'idée est là.
la source
Même l'utilisation de stack ne convertira pas un algorithme récursif en itératif. La récursivité normale est une récursion basée sur la fonction et si nous utilisons la pile, elle devient alors une récursion basée sur la pile. Mais c'est toujours la récursivité.
Pour les algorithmes récursifs, la complexité spatiale est O (N) et la complexité temporelle est O (N). Pour les algorithmes itératifs, la complexité spatiale est O (1) et la complexité temporelle est O (N).
Mais si nous utilisons des choses empilées en termes de complexité reste la même. Je pense que seule la récursivité de la queue peut être convertie en itération.
la source
copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];
espace mémoire et la complexité temporelle sont tous deux O (N) en fonction de la taille des données, mais il s'agit clairement d'un algorithme itératif.L' article sur l' élimination des piles et de la récursivité capture l'idée d'externaliser le cadre de pile sur le tas, mais ne fournit pas un moyen simple et reproductible de convertir. En voici un.
Lors de la conversion en code itératif, il faut être conscient que l'appel récursif peut se produire à partir d'un bloc de code arbitrairement profond. Ce ne sont pas seulement les paramètres, mais aussi le point de revenir à la logique qui reste à exécuter et à l'état des variables qui participent aux conditions subséquentes, qui comptent. Vous trouverez ci-dessous un moyen très simple de convertir en code itératif avec le moins de modifications.
Considérez ce code récursif:
Code itératif:
Remarquez comment la structure du code reste fidèle à la logique récursive et les modifications sont minimes, entraînant moins de bogues. A titre de comparaison, j'ai marqué les changements avec ++ et -. La plupart des nouveaux blocs insérés, à l'exception de v.push_back, sont communs à toute logique itérative convertie
+++++++++++++++++++++++++
------------------------
+++++++++++++++++++++++++
-------------------------
+++++++++++++++++++++++++
-------------------------
+++++++++++++++++++++++++
-------------------------
la source
stackitem
objets sont alloués avec une valeur de poubelle pourra
. Tout fonctionne toujours dans le cas le plus similaire, mais devraitra
par coïncidence être 1 ou 2, vous obtiendrez un comportement incorrect. La solution consiste à initialiserra
à 0.stackitem
ne doit pas être poussé sans initialisation. Mais oui, l'initialisation à 0 entraînerait des erreurs.v.pop_back()
instruction à la place?Recherchez "Style de passage de continuation" sur Google. Il existe une procédure générale de conversion vers un style récursif de queue; il existe également une procédure générale pour transformer les fonctions récursives de queue en boucles.
la source
Juste tuer le temps ... Une fonction récursive
peut être converti en
la source
Généralement, la technique pour éviter le débordement de pile est pour les fonctions récursives est appelée technique de trampoline qui est largement adoptée par les développeurs Java.
Cependant, pour C # il y a un peu d'aide méthode ici qui transforme votre fonction récursive à itérative sans nécessiter à la logique de changement ou de rendre le code en compréhensible. C # est un langage tellement agréable que des choses incroyables sont possibles avec.
Il fonctionne en enveloppant des parties de la méthode par une méthode d'assistance. Par exemple, la fonction récursive suivante:
Se transforme en:
la source
En pensant aux choses qui ont réellement besoin d'une pile:
Si nous considérons le modèle de récursivité comme:
Par exemple, la tour classique de Hanoi
Cela peut être traduit en une boucle fonctionnant sur une pile explicite, en la reformulant comme suit:
Pour la tour de Hanoi, cela devient:
Il y a ici une grande flexibilité quant à la façon dont vous définissez votre pile. Vous pouvez faire de votre pile une liste d'
Command
objets qui font des choses sophistiquées. Ou vous pouvez aller dans la direction opposée et en faire une liste de types plus simples (par exemple, une "tâche" pourrait être 4 éléments sur une pile deint
, plutôt qu'un élément sur une pile deTask
).Tout cela signifie que la mémoire de la pile se trouve dans le tas plutôt que dans la pile d'exécution Java, mais cela peut être utile dans la mesure où vous avez plus de contrôle sur celle-ci.
la source
Un modèle à rechercher est un appel de récursivité à la fin de la fonction (ce qu'on appelle la récursion de queue). Cela peut facilement être remplacé par un certain temps. Par exemple, la fonction foo:
se termine par un appel à foo. Cela peut être remplacé par:
ce qui élimine le deuxième appel récursif.
la source
Une question qui avait été fermée en double de celle-ci avait une structure de données très spécifique:
Le nœud avait la structure suivante:
La fonction de suppression récursive ressemblait à:
En général, il n'est pas toujours possible d'éviter une pile de fonctions récursives qui s'appellent plusieurs fois (voire une fois). Cependant, pour cette structure particulière, c'est possible. L'idée est d'aplatir tous les nœuds en une seule liste. Pour ce faire, placez le nœud actuel
child
à la fin de la liste de la ligne supérieure.Cette technique peut être appliquée à toute structure liée aux données qui peut être réduite à un DAG avec un ordre topologique déterministe. Les nœuds enfants actuels sont réorganisés de sorte que le dernier enfant adopte tous les autres enfants. Ensuite, le nœud actuel peut être supprimé et la traversée peut ensuite être itérée jusqu'à l'enfant restant.
la source
La récursivité n'est rien d'autre que le processus d'appel d'une fonction de l'autre seulement ce processus se fait en appelant une fonction par elle-même. Comme nous le savons, lorsqu'une fonction appelle l'autre fonction, la première fonction enregistre son état (ses variables) puis passe le contrôle à la fonction appelée. La fonction appelée peut être appelée en utilisant le même nom de variables ex fun1 (a) peut appeler fun2 (a). Lorsque nous appelons récursivement, rien de nouveau ne se produit. Une fonction s'appelle en passant le même type et similaire dans les variables de nom (mais évidemment les valeurs stockées dans les variables sont différentes, seul le nom reste le même). Mais avant chaque appel, la fonction enregistre son état et ce processus de sauvegarde se poursuit. L'ECONOMIE SE FAIT SUR UNE PILE.
MAINTENANT LA PILE ENTRE EN JEU.
Donc, si vous écrivez un programme itératif et enregistrez l'état sur une pile à chaque fois, puis que vous sortez les valeurs de la pile si nécessaire, vous avez réussi à convertir un programme récursif en programme itératif!
La preuve est simple et analytique.
En récursivité, l'ordinateur maintient une pile et en version itérative, vous devrez maintenir manuellement la pile.
Pensez-y, il suffit de convertir un programme récursif de recherche en profondeur (sur les graphiques) en un programme itératif dfs.
Bonne chance!
la source
Un autre exemple simple et complet de transformation de la fonction récursive en fonction itérative à l'aide de la pile.
la source
Une description approximative de la façon dont un système prend une fonction récursive et l'exécute à l'aide d'une pile:
Cela visait à montrer l'idée sans détails. Considérez cette fonction qui imprimerait les nœuds d'un graphique:
Par exemple graphique: A-> B A-> C show (A) afficherait B, A, C
Les appels de fonction signifient enregistrer l'état local et le point de continuation afin que vous puissiez revenir, puis sauter la fonction que vous souhaitez appeler.
Par exemple, supposons que show (A) commence à s'exécuter. L'appel de fonction sur la ligne 3. show (B) signifie - Ajouter un élément à la pile signifiant "vous devrez continuer à la ligne 2 avec le noeud d'état variable local = A" - Aller à la ligne 0 avec le noeud = B.
Pour exécuter du code, le système exécute les instructions. Lorsqu'un appel de fonction est rencontré, le système envoie les informations dont il a besoin pour revenir à l'endroit où il se trouvait, exécute le code de la fonction et, une fois la fonction terminée, affiche les informations indiquant où il doit aller pour continuer.
la source
Ce lien fournit quelques explications et propose l'idée de garder "emplacement" pour pouvoir se rendre à l'endroit exact entre plusieurs appels récursifs:
Cependant, tous ces exemples décrivent des scénarios dans lesquels un appel récursif est effectué un nombre fixe de fois. Les choses deviennent plus difficiles lorsque vous avez quelque chose comme:
la source
Il existe un moyen général de convertir un parcours récursif en itérateur en utilisant un itérateur paresseux qui concatène plusieurs fournisseurs d'itérateurs (expression lambda qui renvoie un itérateur). Voir ma conversion de la traversée récursive en itérateur .
la source
Mes exemples sont en Clojure, mais devraient être assez faciles à traduire dans n'importe quelle langue.
Étant donné cette fonction qui
StackOverflow
s pour les grandes valeurs de n:nous pouvons définir une version qui utilise sa propre pile de la manière suivante:
où
return
est défini comme:Cela fonctionne également pour les fonctions plus complexes, par exemple la fonction ackermann :
peut se transformer en:
la source