Bonjour, Habr! Je vous présente la traduction de l'article "Suppression d'une récursivité en Python, partie 1" par Eric Lippert.
Au cours des 20 dernières années, j'ai admiré la simplicité et la puissance de Python, même si je n'ai jamais vraiment travaillé avec lui ni étudié en détail.
Récemment, je l'ai regardé de près - et il s'est avéré que c'était une très belle langue.
Une récente question sur StackOverflow m'a fait me demander comment convertir un algorithme récursif en algorithme itératif, et il s'est avéré que Python était un assez bon langage pour cela.
Le problème rencontré par l'auteur de la question était le suivant:
- Le joueur est dans une cellule arbitraire sur un champ numéroté;
- Le but est de revenir à la cellule numéro 1;
- Si le joueur est sur une case paire, il paie une pièce et va jusqu'à la cellule n ° 1;
- Si le joueur est sur une case impaire, il peut payer 5 pièces et aller directement à la première case ou payer une pièce et faire un pas vers la case n ° 1 - sur une case paire.
La question est: quelle est la quantité minimale de pièces que vous devez payer pour revenir de la cellule actuelle à la première.
La tâche a une solution récursive évidente:
def cost(s): if s <= 1: return 0 if s % 2 == 0: return 1 + cost(s // 2) return min(1 + cost(s - 1), 5)
Cependant, ce programme s'est écrasé, atteignant la profondeur maximale de récursivité, probablement en raison du fait que l'auteur de la question a expérimenté de très grands nombres.
Par conséquent, la question se pose: comment transformer un algorithme récursif en un algorithme itératif en Python?
Avant de commencer, je tiens à noter qu'il existe bien sûr des solutions plus rapides à ce problème spécifique, en soi ce n'est pas très intéressant.
Au contraire, cette tâche n'a servi que de point de départ à la question de savoir comment, dans le cas général, se débarrasser d'un seul appel récursif dans un programme Python.
Le fait est que vous pouvez convertir n'importe quelle méthode récursive simple et vous débarrasser de la récursivité, et ce n'est qu'un exemple à portée de main.
La technique que je vais montrer, bien sûr, ne correspond pas exactement à la façon dont Python est écrit, probablement une solution de style Python utiliserait des générateurs ou d'autres fonctionnalités du langage.
Ce que je veux montrer ici, c'est comment se débarrasser de la récursivité en utilisant une séquence de petites transformations sûres, menant la fonction à une forme dans laquelle il est facile de remplacer la récursivité par une itération.
Pour commencer, voyons comment amener le programme dans ce formulaire.
À la première étape de notre conversion, je veux que les calculs effectués avant l'appel récursif soient réduits au calcul de l'argument, et les calculs, après l'appel récursif, doivent être effectués dans une méthode distincte qui accepte le résultat de l'appel récursif.
def add_one(n): return n + 1 def get_min(n): return min(n + 1, 5) def cost(s): if s <= 1: return 0 if s % 2 == 0: argument = s // 2 result = cost(argument) return add_one(result) argument = s - 1 result = cost(argument) return get_min(result)
La deuxième étape que je veux faire est le calcul de l'argument dans une fonction distincte:
Dans la troisième étape, je veux ajouter une fonction d'assistance qui sélectionnera la fonction de continuation qui est appelée après son retour de récursivité.
Notez que la fonction d'assistance renvoie une fonction.
Maintenant, nous l'écrivons sous une forme plus générale et concise:
On peut voir que chaque modification apportée a conservé le sens du programme.
Maintenant, la vérification de la parité du nombre est effectuée deux fois, bien qu'avant les modifications il y ait eu une vérification.
Si nous le voulons, nous pouvons résoudre ce problème en combinant deux fonctions d'assistance en une seule qui renvoie un tuple.
Mais ne nous inquiétons pas de cela dans le cadre de cette tâche.
Nous avons réduit notre méthode récursive à la forme la plus générale.
- Dans le cas de base:
- calculer la valeur à renvoyer;
- le retourner.
- Dans un cas non élémentaire:
- calculer l'argument de récursivité;
- faire un appel récursif;
- calculer la valeur de retour;
- le retourner.
Une chose importante à laquelle vous devez faire attention à cette étape est after ne doit pas contenir cost appels de cost lui-même.
La méthode que je montre ici supprime un seul appel récursif.
Si vous avez 2 récursions ou plus, nous avons besoin d'une solution différente.
Une fois que nous avons amené notre algorithme récursif sous cette forme, il est déjà facile de le convertir en itératif.
L'astuce consiste à imaginer ce qui se passe dans un programme récursif.
Comment nous faisons une descente récursive: nous appelons get_argument avant l'appel récursif et appelons la fonction after après le retour de la récursivité.
Autrement dit, tous les appels à get_argument se produisent avant tous les appels à after .
Par conséquent, nous pouvons convertir cela en 2 cycles: le premier appelle get_argument et forme une liste de fonctions après , et le second appelle toutes les fonctions après :
Plus de récursivité!
Cela ressemble à de la magie, mais tout ce que nous faisons ici est le même que la version récursive du programme, et dans le même ordre.
Cet exemple reflète la pensée que je répète souvent à propos de la pile d'appels: son but est de communiquer ce qui va se passer ensuite, et non ce qui s'est déjà produit!
La seule information utile sur la pile d'appels dans la version récursive du programme est la valeur après , car cette fonction est appelée ensuite, et tout le reste sur la pile n'est pas important.
Au lieu d'utiliser la pile d'appels comme un moyen inefficace et encombrant de stocker la pile après , nous pouvons simplement stocker la pile de fonctions après .
La prochaine fois, nous examinerons une manière plus complexe de supprimer la récursivité en Python.