36 - Récursivité avec Python
La récursivité est un moyen efficace de programmer. Elle est très courante même si nous n'en avons pas encore parlé car elle nécessite d'avoir des connaissances assez précises des fonctions pour en comprendre réellement le fonctionnement.
Ca tombe bien : c'est maintenant votre cas.
Prérequis : les activités précédentes sur les fonctions
Logiciel nécessaire pour l'activité : Python 3 : Thonny, IDLE ...
Présentation du cours : open document ou pdf
Evaluation ✎ : questions 13-14-15-16-17-18-19-20
Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)
1 - Découverte du principe
01° Sans lancer ce programme, écrire ce qu'il va afficher à l'écran à votre avis. Lancer ensuite le programme pour visualiser le résultat réel.
1
2
3
4
5
6 | |
...CORRECTION...
On crée une boucle bornée partant de 5, décroissante avec un pas de -1 et dont la borne limite exclue est -1. x varie donc de 5 à 0.
Appel de p(5)
Appel de p(4)
Appel de p(3)
Appel de p(2)
Appel de p(1)
Appel de p(0)
Il s'agit donc d'un appel successif à des fonctions. Une simple boucle.
Mais nous pouvons faire la même chose avec un appel récursif : la fonction peut alors faire appel à une autre instance d'elle-même (une nouvelle version d'elle-même).
02° Observer le programme ci-dessous sans le lancer.
- Quel va être le premier affichage sur la console ?
- Le programme va-t-il s'arrêter ou va-t-on lancer un nouvel appel ?
- Quel appel ?
- Que va-t-il afficher ? Que va-t-il activer ?
1
2
3
4
5
6
7
8
9 | |
...CORRECTION...
On lance l'appel p(5). Cela va provoquer via la ligne 3 l'affichage suivant :
Appel de p(5)
Comme x contient 5, on va en ligne 7.
On lance alors l'appel p(4). Cela va provoquer via la ligne 3 l'affichage suivant :
Appel de p(4)
Comme x contient 4, on va en ligne 7.
On lance alors l'appel p(3). Cela va provoquer via la ligne 3 l'affichage suivant :
Appel de p(3)
Comme x contient 3, on va en ligne 7.
On lance alors l'appel p(2). Cela va provoquer via la ligne 3 l'affichage suivant :
Appel de p(2)
Comme x contient 2, on va en ligne 7.
On lance alors l'appel p(1). Cela va provoquer via la ligne 3 l'affichage suivant :
Appel de p(1)
Comme x contient 1, on va en ligne 7.
On lance alors l'appel p(0). Cela va provoquer via la ligne 3 l'affichage suivant :
Appel de p(0)
Comme x contient 0, on ne relance plus d'appel.
03° Lancer le programme sur Python Tutor pour comparer à votre lecture du code.
Combien de versions de la fonction sont actives en même temps au maximum 1 ou 5 ?
Le schéma de principe des appels récursifs pour réaliser les appels est donc différents du cas itératif :
On remarque tout de suite qu'il est nécessaire lors de l'utilisation de la récursivité d'avoir une condition d'arrêt qui mène à un cas de base : un cas qui ne provoque plus d'appels récursifs. Sans lui, on lancerait des appels à l'infini.
Ici, la condition d'arrêt est donc x == 0 (ligne 4) puisque cette expression évaluée à True ne provoque pas de nouvel appel à p().
1
2
3
4
5
6
7
8
9 | |
04° Les lignes 4 et 5 sont-elles vraiment nécessaires ici ? Comment pourrait-on écrire cette fonction avec un test IF sans ELSE ?
...CORRECTION...
Non. Elles permettent juste de bien comprendre et montrer qu'il y a deux cas :
- Le cas de base, non récursif
- Le cas récursif : on fait encore appel à la fonction ou la procédure
1
2
3
4
5
6
7 | |
05° Expliquer le problème qu'on va rencontrer sur cette fonction après avoir analysé le programme. Il y a un problème. Cherchez bien.
1
2
3
4
5
6
7
8
9 | |
...CORRECTION...
La récursivité provoque une boucle infinie : on ne pourra jamais atteindre la condition d'arrêt puisque les paramètres x deviennent de plus en plus grands. On ne pourra donc jamais valider la condition x == 0.
06° Même question.
1
2
3
4
5
6
7
8
9 | |
...CORRECTION...
La récursivité provoque une boucle infinie : on ne pourra jamais atteindre le cas de base non-recursif puisque le paramètre x vaut successivement 5, 3, 1, -1, -3...
Encore une fois, on ne parviendra pas à s'arrêter.
Pour l'instant, nous n'avons utilisé que des "procédures", des fonctions qui ne renvoient rien. Il s'agit donc d'une simple succession d'action, pas d'un calcul mémorisé.
Voyons un premier exemple classique : le calcul des séries arithmétiques, rencontrées dans la partie Algorithmique.
Pour rappel, voici la formule permettant de calculer la série arithmétique des nombres de 1 à n :
formule 107° Réaliser une fonction non récursive permettant de calculer cette série, sans utiliser la formule. Il faut imposer à votre fonction de calculer 1 + 2 + 3 + ... jusqu'à n.
On notera que la fonction fournie possède déjà :
- Une documentation pouvant servir au module doctest.
- Deux assertions permettant d'imposer la précondition sur le paramètre n qui doit être entier et strictement positif.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26 | |
...CORRECTION...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29 | |
Comme on le voit, il y a une grande différence entre le code informatique permettant de calculer cette série (on doit créer une boucle et une variable permettant de stocker les additions successives) et sa définition mathématique (une simple addition 1 + 2 +3 + 4 + ...).
La programmation récursive va nous permettre de coder une fonction dont le code se rapproche de la version mathématique.
Si on utilise cette définition, on doit alors réfléchir de cette façon :
f(5) = 5 + f(4)
f(5) = 5 + 4 + f(3)
f(5) = 5 + 4 + 3 + f(2)
f(5) = 5 + 4 + 3 + 2 + f(1)
f(5) = 5 + 4 + 3 + 2 + 1 + f(0)
f(5) = 5 + 4 + 3 + 2 + 1 + 0
EN GROUPE° Appliquer l'algorithme suivant applicable à un humain.
- Si on vous demande serie(n) avec n = 1, vous pouvez répondre 1 à la personne qui vous a contacté.
- Sinon si vous êtes le dernier de la liste, vous pouvez calculer directement le résultat puis répondre à la personne qui vous a contacté.
- Sinon, c'est le cas récursif :
- Vous lancez la demande serie(n-1) à la personne suivante et vous attendez qu'elle réponde un jour.
- Une fois que vous connaissez sa réponse, il vous suffit de répondre n + réponse à la personne qui a fait appel à vous.
08° Analyser la fonction récursive. Comparer son code à la version récursive de la somme des n premiers entiers.
Questions :
- pourquoi est-ce bien une fonction et pas une simple procédure ?
- quelle est la version la plus proche de la version mathématique : la fonction itérative ou la fonction récursive ?
1
2
3
4
5
6
7
8
9 | |
Le résultat des appels dans la console affiche encore l'activation progressive des fonctions.
...CORRECTION...
Il s'agit bien d'une fonction car cette fois on renvoie un résultat.
On voit bien que c'est cette version récursive qui se rapproche le plus de la définition mathématique précédente. Plus de variable temporaire à créer. On a bien uniquement les deux cas : le cas de base et le cas itératif.
1 - Fonction récursive
Une fonction récursive est une fonction qui, pour répondre, peut lancer un appel à une autre instance d'elle même.
Elle doit posséder au moins deux modes de calcul :
- Un cas récursif où on a besoin de lancer à autre appel à la fonction (en modifiant éventuellement les paramètres d'appel)
- Un cas de base non récursif qui permet d'obtenir une possibilité d'arrêt. On obtient ce cas lorsque la condition d'arrêt est validée.
Si la réponse de f(5) est return 5 + f(4), alors f(5) doit attendre que f(4) réponde pour évaluer sa propre réponse. Tant que f(4) ne répond pas, f(5) est bloquée et en attente.
On notera qu'il faut être vigilant sur cette condition d'arrêt : elle doit pouvoir être atteinte, sinon on obtient une boucle infinie d'appels récursifs.
Pour rappel, voici les schémas de principe illustrant le mode de fonctions des fonctions itératives et des fonctions récursives :
Fonction itérative
Fonction récursive
EN GROUPE° Appliquer l'algorithme suivant applicable à un humain.
Nouvelle tâche : "Quelle est la taille de la personne la plus grande du groupe" ?
- Si vous êtes le dernier de la liste : vous répondez en transmettant votre taille à la personne qui a fait appel à vous.
- Sinon, c'est le cas récursif :
- Vous posez la question à la personne suivante et vous attendez sa réponse
- Une fois que vous connaissez sa réponse, vous sélectionnez la plus grande valeur entre sa réponse et votre propre taille. Vous pouvez alors répondre cette valeur maximum à la personne qui a fait appel à vous.
EN GROUPE° Appliquer l'algorithme suivant applicable à un humain.
Nouvelle tâche : "Quelqu'un a t-il mangé de la pizza hier" ?
- Si vous avez mangé de la pizza hier, vous pouvez répondre OUI à la personne qui a fait appel à vous.
- Sinon si vous êtes le dernier, vous pouvez répondre NON à la personne qui a fait appel à vous.
- Sinon, c'est le cas récursif :
- Vous posez la question à la personne suivante et vous attendez sa réponse
- Une fois que vous connaissez sa réponse, vous n'avez plus qu'à transmettre cette réponse à la personne qui a fait appel à vous.
2 - Empilement et dépilement
Maintenant que vous avez compris le déroulement global d'une fonction récursive, regardons comment fait l'ordinateur concrétement pour réaliser ce calcul.
Regardons à nouveau notre fonction.
1
2
3
4
5
6
7
8
9 | |
Lors de l'appel à f(5), on voit donc que la fonction va devoir renvoyer 5 + f(4). Pour faire cela, elle va donc devoir attendre la réponse de f(4).
09° La fonction f(5) peut-elle renvoyer directement un résultat au programme qui l'a appelé ou doit-elle d'abord calculer quelque chose ?
...CORRECTION...
On constate bien que la fonction ne peut rien renvoyer pour l'instant : elle doit renvoyer 5 + f(4) mais ne connait pas le résulat de f(4).
Avant de renvoyer le résultat de f(5) au programme principal, il va donc falloir renvoyer le résultat de f(4) à f(5).
10° Observer le déroulement du programme sur le site Python Tutor, ou utiliser le mode DEBUG progressif de Thonny si vous ne parvenez pas à aller sur Python Tutor.
Vous devriez avoir visualisé le déroulement progressif du calcul :
- Le programme principal active f(5). Cette fonction veut renvoyer 5 + f(4). On met donc cette fonction f(5) en pause et on lance f(4). Pour répondre f(5) devra attendre la réponse de f(4).
- Cette fonction f(4) veut renvoyer 4 + f(3). On met donc cette fonction f(4) en pause et on lance f(3).
- Cette fonction f(3) veut renvoyer 3 + f(2). On met donc cette fonction f(3) en pause et on lance f(2).
- Cette fonction f(2) veut renvoyer 2 + f(1). On met donc cette fonction f(2) en pause et on lance f(1).
- Cette fonction f(1) veut renvoyer 1 + f(0). On met donc cette fonction f(1) en pause et on lance f(0).
- Cette fonction f(1) peut enfin répondre sans attendre et va renvoyer 0. C'est le cas de base.
Mais, au fait, comment est-ce que ça fonctionne ? Comment une fonction sait à qui répondre une fois qu'elle a fini son travail ?
2 - Culture générale : pile d'exécution, call stack en anglais
La pile d'exécution est la structure de données dans laquelle on enregistre les informations sur les appels de fonctions dans un programme informatique. C'est grace à elle qu'on sait "qui appelle qui" et quelle réponse donner à qui.
Sans rentrer dans les détails, on va donc empiler des blocs d'informations à partir d'une adresse de départ.
Chacun appel de fonction génère son bloc de données.
Chaque bloc contient notamment :
- l'adresse à laquelle le return doit renvoyer la réponse (le bloc du dessous normalement)
- Les paramètres enregistrés lors de l'appel
- les variables locales qu'elle utilise lors de son exécution
Si nous simplifions la notion pour n'en garder que ce qui nous interesse aujourd'hui, voici le contenu de la pile au fur et à mesure de l'exécution de notre fonction f(5)
.On commence avec f(5) qui demande l'appel de f(4)
Ensuite f(4) demande l'appel de f(3)
On continue avec f(3) demande l'appel de f(2)
Et, nous allons accumuler sur cette pile, les appels récursifs jusqu'à arriver à la condition d'arrêt. Ici, elle apparaît lors de l'appel à f(0).
Voici la pile d'exécution lorsqu'on en arrive là :
En anglais, on dira call stack.
11° Continuer sur une feuille cette autre représentation des appels successifs imbriqués les uns dans les autres.
f(5) va renvoyer 5 + f(4)
|
va renvoyer 4 + f(3)
|
...CORRECTION...
f(5) renvoie 5 + f(4)
|
va renvoyer 4 + f(3)
|
va renvoyer 3 + f(2)
|
va renvoyer 2 + f(1)
|
va renvoyer 1 + f(0)
|
renvoie 0
12° Continuer cette dernière représentation des appels successifs imbriqués les uns dans les autres.
Appel à f(5) va renvoyer 5 + f(4)
Appel à f(4) va renvoyer 4 + f(3)
Appel à ...
...CORRECTION...
Appel à f(5) va renvoyer 5 + f(4)
Appel à f(4) va renvoyer 4 + f(3)
Appel à f(3) va renvoyer 3 + f(2)
Appel à f(2) va renvoyer 2 + f(1)
Appel à f(1) va renvoyer 1 + f(0)
Appel à f(0) renvoie 0
3 - Dépilement
Une fois le cas de base atteint, on ne rajoute plus rien sur la pile.
On peut maintenant calculer les réponses à renvoyer aux fonctions ayant lancé les appels pour qu'elles puissent évaluer leurs propres réponses.
Nous venons de voir que f(0) renvoie 0 à f(1).
Donc f(1) renvoie 1+0 et donc 1 à f(2).
Donc f(2) renvoie 2+1 et donc 3 à f(3).
Donc f(3) renvoie 3+3 et donc 6 à f(4).
Donc f(4) renvoie 4+6 et donc 10 à f(5).
Enfin f(5) renvoie 5+10 et donc 15 au programme qui en a fait initialement appel.
Et voilà donc le schéma global de l'empilement et du dépilement :
✎ 13° Expliquer la réponse obtenue après dépilement en utilisant cette autre représentation de l'empilement.
f(5) renvoie 5 + f(4)
|
renvoie 4 + f(3)
|
renvoie 3 + f(2)
|
renvoie 2 + f(1)
|
renvoie 1 + f(0)
|
renvoie 0
✎ 14° Expliquer la réponse obtenue après dépilement en utilisant cette autre représentation de l'empilement.
Appel à f(5) renvoie 5 + f(4)
Appel à f(4) renvoie 4 + f(3)
Appel à f(3) renvoie 3 + f(2)
Appel à f(2) renvoie 2 + f(1)
Appel à f(1) renvoie 1 + f(0)
Appel à f(0) renvoie 0
4 - Exercices de programmation
Voyons maintenant si vous parvenez à réaliser vous-mêmes quelques fonctions récursives, simples ou pas.
✎ 15° Réaliser une fonction produit() récursive correspondant à cette manière de voir la multiplication : 5 * 6 = 5+5+5+5+5+5.
Attention aux spécifications d'entrée : n et p sont des entiers, p étant positif.
✎ 16° Quel est le cas de base (et la condtion d'arrêt) de votre fonction ? Montrer son empilement et son dépilement pour l'appel produit(5,3)
✎ 17° Réaliser une fonction puissance() récursive correspondant à cette manière de voir la multiplication : 56 = 5*5*5*5*5*5.
Attention aux spécifications d'entrée : x et n sont des entiers, n étant positif.
✎ 18° Quelle est la condition d'arrêt et le cas de base de votre fonction ? Montrer son empilement et son dépilement pour puissance(5,3)
✎ 19° Réaliser une fonction factorielle() récursive correspondant à la définition de la factorielle d'un entier : 5! = 5*4*3*2*1.
Attention aux spécifications d'entrée : n est un entier positif.
✎ 20° Quelle est la condition d'arrêt et le cas de base de votre fonction ? Montrer son empilement et son dépilement pour factorielle(5)
5 - Récursivité dans la nature
La nature regorge de structure de ce genre. Vous avez déja regardé un brocolis de près ?
Voici un programme comportant une procédure permettant de tracer la courbe de Kock.
21° Tester le programme avec des valeurs plus petites de n valant 0, puis 1, puis 2... pour voir le principe.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | |
6 - FAQ
En terme de place en mémoire, ça donne quoi ?
On dit souvent à propos de la récursivité qu'une fonction s'appelle elle-même. En réalité, c'est faux.
Il faut voir la déclaration d'une fonction comme la déclaration d'un mode d'emploi, d'une notice mais c'est tout.
Par contre, lorsqu'on lance un appel à une fonction, on crée une vraie fonction concrête avec son propre espace mémoire.
Ainsi, si vous lancez l'appel de f(5) et un autre appel à f(5), vous allez en réalité avoir deux espaces mémoires différents : chacune de ces deux fonctions aura son propre espace des noms et ses propres variables.
Pourquoi cette précision sur la place mémoire ?
Pour signaler que la récursivité n'est pas un moyen magique de trouver la solution d'un problème. Si, en moyenne, une fonction trace() a besoin d'une place mémoire de 800 octets pour répondre, et qu'on a besoin de 1000 appels récursifs pour répondre au problème, au plus haut de l'empilement des fonctions, nous aurons donc besoin d'un espace mémoire de 1000*800 octets, soit 800 000 octets, soit 800 ko.
Chaque appel récursif constitue donc une fonction indépendante, ayant ses propres variables, son propre espace des noms ect... Et cet espace occupe la mémoire tant que cette version de la fonction n'a pas pu répondre car elle attend la réponse d'une autre version d'elle-même.
Activité publiée le 10 09 2020
Dernière modification : 07 09 2022
Auteur : ows. h.