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 ...
Evaluation ✎ : questions 13-14-15-16-17-18-19-20
Résumé : Version HTML ou fond blanc ou ou PDF (couleur ou gris)
1 - Principe
01° Sans lancer ce code, écrire ce que va afficher, à votre avis, ce code à l'écran. Lancer ensuite le code 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 itération.
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.
02° Observer le code ci-dessous sans le lancer.
Une fois arrivé en ligne 9,
- 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 code pour comparer à votre lecture du code.
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 ce code après l'avoir analysé. 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
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 plus une sorte de 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.
Fonction récursive
Une fonction récursive est par définition une fonction qui, pour répondre, peut lancer un appel à une autre instance d'elle même.
Elle doit en effet 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.
On notera qu'il faut être vigilant sur cette condition d'arrêt : elle doit pouvoir être atteinte, sinon on obtient en théorie une boucle infinie d'appels récursifs.
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 renvoyer5 + f(4). On met donc cette fonction en pause et on lance la suite. f(5)activef(4). Cette fonction veut renvoyer4 + f(3). On met donc cette fonction en pause et on lance la suite.f(4)activef(3). Cette fonction veut renvoyer3 + f(2). On met donc cette fonction en pause et on lance la suite.- ...
Mais du coup, comment est-ce que ça fonctionne ? Comment la fonction sait à qui répondre une fois qu'elle a fini son travail ?
Culture générale : pile d'exécution, cas 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.
Sans rentrer dans les détails, on va donc empiler à partir d'une adresse de départ fondamentalement 3 types d'information pour chaque fonction active :
- Les paramètres enregistrés lors de l'appel
- L'adresse à laquelle le return doit renvoyer la réponse
- 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)
Du coup 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 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 donc de trouver f(0) peut renvoyer 0 à f(1).
Du coup, f(1) peut renvoyer 1+0 soit 1 à f(2).
On continue : f(2) peut renvoyer 2+1 soit 3 à f(3).
Du coup, f(3) va renvoyer 3+3 soit 6 à (4).
f(4) va donc renvoyer 4+6 soit 10 à f(5).
En finalement, f(5) peut renvoyer 5+10 ou 15 au programme principal.
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° Quelle est la condition d'arrêt de votre fonction ? Quel est son cas de base ? Montrer son empilement et son dépilement pour 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 de votre fonction ? Quel est son cas de base ? 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 de votre fonction ? Quel est son cas de base ? 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'une classe. Il s'agit 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 fonction concrête, une sorte d'instance de cette fonction.
Du coup, on devrait plutôt dire qu'une instance d'une fonction lance un appel à une autre instance d'une fonction, et pas "une fonction s'appelle elle-même".
Pourquoi cette précision ?
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 ko.
Chaque appel récursif constitue bien une fonction indépendante, ayant ses propres variables, son propre espace des noms ect...
Activité publiée le 10 09 2020
Dernière modification : 08 03 2021
Auteur : ows. h.