Nous avons vu que les fonctions nous permettent d'organiser et de réutiliser des parties de notre code. Nous avons vu également que les fonctions peuvent être définies à partir d'autres fonctions. Dans cette leçon, nous allons apprendre qu'une fonction peut être définie à partir d'elle-même! Cette approche très utile s'appelle la récursion. La légende dit que "pour comprendre la récursion, il faut d'abord comprendre la récursion."
Exemple
Dans notre leçon sur les boucles, nous avons utilisé une boucle while pour générer la sortie suivante.
5 4 3 2 1 Decollage!Voici un programme qui utilise la récursion pour arriver au même résultat.
Ajoutons-nous quelques instructions print pour nous aider à comprendre ce qui se passe. Cette version du programme lit l'entrée pour déterminer le nombre initial.
Vous pouvez utiliser Tape entrée avec le programme ci-dessus afin d'essayer d'autres valeurs d'entrées. Essayez d'abord avec 0 puis 1.
Quand l'entrée est 5, le programme appelle tout d'abord une copie de la fonction compter avec n=5, ce qui affiche 5 et appelle compter(4). Cela continue jusqu'à compter(0), qui naffiche "Decollage!" et n'appelle plus compter. Quand Python termine d'exécuter l'appel pour n=0 de la fonction compter, Python retourne à la fonction qui l'a appelée, qui n'est autre que l'appel à la fonction compter pour n=1.On retourne ensuite à l'appel pour n=2, etc.
Maintenant c'est à vous d'écrire du code. Modifiez la fonction compter pour qu'elle compte en augmentant plutôt qu'en diminuant.
Maintenant modifions-nous notre programme compter pour qu'il décrémente par 2: p. ex. quand on commence à 5 la sortie sera 5, 3, 1, Decollage! Nous devons changer l'argument de la fonction de n-1 en n-2. Y a-t-il autre chose à changer?
Vous pouvez voir que ce programme ne fait pas ce que nous souhaitons. Il affiche 5, 3, 1, comme nous le voulions mais au lieu de s'arrêter, il continue avec -1, -3, -5 et s'exécute sans fin. (Plus exactement, il tombe à cours de temps et de mémoire car chaque appel récursive utilise un peu plus de mémoire de travail.)
Lorsque l'on crée une fonction récursive, il faut ensurer que la séquence des appels ne continue pas indéfiniment! Modifiez le programme compterParDeux pour qu'il s'arrête correctement à 1 (ou 2 si n est pair) et affiche 'Decollage!'.
Définir des Fonctions Récursives
Une fonction récursive signifie tout simplement une fonction qui s'appelle elle-même. Mais il doit y avoir des conditions dans lesquelles la fonction ne s'appelle pas elle-même sinon le programme s'exécute pour toujours (nous l'avons vu précédemment). La condition d'arrêt est la partie de la fonction récursive qui fait qu'elle ne va plus s'appeler elle-même. Dans l'exemple ci-dessus, c'était n<=0. Définir une fonction récursive demande de bien choisir cette condition d'arrêt et de s'assurer que la séquence d'appels de la fonction arrivera à la condition d'arrêt.
Dans l'exercice suivant, la condition d'arrêt a déjà été définie pour vous mais vous devez écrire le reste de la fonction récursive.
Maintenant vous allez écrire une fonction qui appelle la fonction récursive sommeDigital comme sous-fonction.
Exercices
def pgcd(a, b): if b == 0: return a return pgcd(b, a % b) print(pgcd(20, 12))
Les mathématiciens pensent que toutes les séquences de grêlon atteignent 1, quelque soit la valeur de n avec laquelle on commence. Cependant, personne n'a pu le prouver jusqu'à aujourd'hui.
Listes imbriquées
Nous discutons maintenant une application intéressante et naturelle de la récursivité. Une liste imbriquée est une liste avec quelques listes à l'intérieur des autres, peut-être plusieurs fois. Par exemple, certaines listes imbriquées d'entiers sont [[1, 2], [9, 10]] en plus de [[1], 2] et x = [[1], 2, [3, [[4]]]]. L'exemple liste imbriquée dernière est une liste de trois éléments: x[0]==[1] à commencer, ensuite x[1]==2, et x[2]==[3, [[4]]]. (Par conséquent len(x)=3.) Notez qu'une liste comme [1, 2, 3] est également considérée comme une liste imbriquée. Peut-on écrire une fonction pour trouver la somme totale de n'importe quelle liste imbriquée des entiers? Par exemple, pour donnée [[5], 2, [10, 8, [[7]]]] il doit retourner la valeur 32.
Cette tâche est difficile pour une boucle while ou for, puisque nous voulons une fonction qui peut prendre des listes imbriquées avec n'importe quelle forme/format. Toutefois, les listes imbriquées ont une structure naturellement récursive: une liste imbriquée est une liste dont chacune des pièces est (a) un nombre entier ou (b) une liste imbriquée. Et, lorsque l'on calcule la somme de chaque sous-partie de la liste principale, le total de ces valeurs correspond à la somme globale. Nous pouvons exprimer cela avec le code suivant; il utilise isinstance(x, int) qui nous donne une valeur booléenne indiquant si x est de type entier (par opposition à une liste).
Voyez-vous comment la récursivité est utilisée pour décomposer chaque liste imbriquée en parties plus petites? Par exemple, listeImbriqueeSomme([1, [3, 4], 5]) fait un total de 6 appels récursifs: la première, puis sur 1, puis sur [3, 4], puis sur 3 et sur 4, (après laquelle la somme [3, 4] est retourné comme 7) et enfin sur 5 (après laquelle le montant global 13 est obtenu).
Règle d'or
La récursion est aussi liée aux fractales - des images qui contiennent de multiples copies d'elle-même. La bannière en haut de cette page en est un exemple. Le prochain exercice crée un motif répété simple qui utilise la récursion.
Bravo! Vous pouvez passer à la prochaine leçon.
