16: Récursivité

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.

Exemple
Un compte à rebours utilisant la récursion

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.

Exemple
Un compte à rebours utilisant la récursion
Vous pouvez entrer des données pour le programme dans la boîte ci-dessous.

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.

Exercice de code : Décollage inversé
Ecrivez une fonction récursive decompter(n) qui affiche 'Decollage!' suivi des nombres 1 à n sur des lignes séparées. Indice
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

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?

Exemple
Tentative de compte à rebours par incréments de 2

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!'.

Exercice de code : Double Time
Modifiez ce programme pour qu'il compte à rebours avec un incrément de 2.
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

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.

Exercice de code : Somme digitale
La somme digitale d'une nombre n est la somme de ces chiffres. Ecrivez une fonction récursive sommeDigital(n) qui prend en entrée un nombre positif n et retourne sa somme digitale. Par exemple, sommeDigital(2019) retournera 12 car 2+0+1+9=12. Indice #1 Indice #2
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

Maintenant vous allez écrire une fonction qui appelle la fonction récursive sommeDigital comme sous-fonction.

Exercice de code : Racine digitale
La racine digitale d'un entier non-négatif n est calculée de la manière suivante. Commencez par additionner tous les chiffres de n. Les chiffres du résultat de cette somme sont ensuite ajouté et le processus continue jusqu'à ce que l'on obtienne un résultat à un seul chiffre. Par exemple, la racine digitale de 2019 est 3 car 2+0+1+9=12 et 1+2=3. Ecrivez une fonction récursive racineDigitale(n) qui retourne la racine digitale de n.
Assumez que vous avez à disposition la fonction sommeDigitale.
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

Exercices

Exercice à réponse courte : PGCD
Quelle est la sortie de ce programme récursif?

def pgcd(a, b):
  if b == 0: return a
  return pgcd(b, a % b)
print(pgcd(20, 12))
Correct! This remarkably short program computes the greatest common divisor of two numbers. This is known as the Euclidean Algorithm, one of the oldest known algorithms.

Exercice de code : Grêlon
Une suite de grêlon commençant avec un nombre positif n est générée en appliquant les deux règles suivantes. Si n est paire, le nombre suivant dans le série est n/2. Si n est impair, le nombre suivante dans la  série est 3*n+1. En répétant ce processus, on génère la séquence de grêlon. Ecrivez une fonction récursive grelon(n) qui affiche la séquence de grêlon commençant à n. Arrêtez quand la séquence arrive à 1 (sinon la séquence boucle indéfiniment 1, 4, 2, 1, 4, 2, ...)
Par exemple quand n=5, votre programme doit afficher la suite:

5
16
8
4
2
1
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

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 naturel de la récursivité. Une liste imbriquée est une liste avec queleques 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).

Exemple : Sommant une liste imbriquée
Le calcul de la somme des éléments dans une liste imbriquée avec une fonction récursive. Une fois que vous appuyez sur Exécuter, vous verrez sa valeur sur certains tests.
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

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).

Exercice de code : Recherchant dans une liste imbriquée
En écrivant quelque chose qui ressemble listeImbriqueeSomme, définir une fonction récursive

listeImbriqueeContient(LI, cible)
qui prend une liste imbriquée LI des entiers et un entier cible, et indique si cible est contenu n'importe où dans la liste imbriquée. Votre code doit retourner la valeur booléenne True quand elle est contenue dans la liste imbriquée, et False autement.
Par exemple, listeImbriqueeContient([1, [2, [3], 4]], 3) devrait donner True et listeImbriqueeContient([1, [2, [3], 4]], 5) devrait donner False.
Entrez instructions de test comme print(mafonction("argument de test")) ci-dessous.

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.

Exercice mêlé : Règle fractale
Mettez dans l'ordre les lignes de code pour créer un programme qui produit un dessin récursif de type règle. Par exemple, pour n=3 le programme devrait afficher.

-
--
-
---
-
--
-
  • def regle(n):
  • regle(n - 1)
  • else:
  • if n == 1:
  • print(n * '-')
  • print('-')
  • regle(n - 1)

Bravo! Vous pouvez passer à la prochaine leçon.