Chapitre 2 : Récursivité
QCM du chapitre 2 : https://miniurl.be/r-5nvw
I- Première approche de la programmation récursive
En programmation, on dit qu'un algorithme est récursif s'il fait appel à lui-même. Dans le cas des fonctions,
on dit qu'une fonction est récursive si elle s'appelle elle-même durant son exécution.
Différence imagée entre itératif et récursif :
Pour faire avancer un robot :
En itératif En récursif
Répéter en boucle : Avancer :
Faire un pas en avant Faire un pas en avant puis Avancer
Exemple :
Essayons d'écrire une fonction qui détermine de façon récursive le prix du livre pour le locataire du 4ème étage.
En Python, cette fonction s'écrirait alors de la façon suivante :
def prix(n):
if n == 0:
Cas de base : valeur pour laquelle le résultat est connu
return 3
else:
return prix(n-1) * 2 Appel récursif : la fonction fait appel à elle-même
(à un autre rang) et place les calculs intermédiaires
en attente dans une pile d'exécution.
L'exécution de cette fonction va alors s'effectuer en 2 phases :
• Une phase de descente :
Prix au 4ème étage = Prix au 3ème étage × 2
Prix au 3ème étage = Prix au 2ème étage × 2
Prix au 2ème étage = Prix au 1er étage × 2
Prix au 1er étage = Prix au RdC × 2
Prix au RdC = 3 euros
- page 1 -
Durant la phase de descente, les calculs intermédiaires qui ne peuvent être résolus par l'ordinateur sont mis "en
mémoire", en attendant de pouvoir être effectués. L'ordinateur place ces calculs en attente dans la mémoire dans
ce qu'on appelle une pile d'exécution, en attendant de pouvoir les résoudre.
• Puis une phase de remontée :
Si l'algorithme est correctement construit, il contient à un moment donné une information qui permet à un des
calculs de s'effectuer : c'est ce qu'on appelle le cas de base.
L'ordinateur qui exécute le programme va alors pouvoir remonter la pile d'exécution et réaliser tous les calculs en
attente :
Prix au 4ème étage = 24 × 2 = 48 euros
Prix au 3ème étage = 12 × 2 = 24 euros
Prix au 2ème étage = 6 × 2 = 12 euros
Prix au 1er étage = 3 × 2 = 6 euros
Prix au RdC = 3 euros
(cas de base)
Plusieurs choses sont à constater et à retenir ici :
• La pile étant stockée dans la RAM le temps que le calcul se termine, si trop d'appels récursifs sont effectués,
la mémoire peut devenir insuffisante et on dit dans ce cas que la pile d'exécution déborde (on parle alors
de dépassement ou débordement de pile - stack overflow en anglais).
• Une fonction récursive contient obligatoirement un appel récursif qui permet à la fonction de s'appeler
elle-même. L'appel récursif doit être construit de façon à rejoindre le cas de base ou de sortir de la fonction.
• L'utilisation d'une fonction récursive permet de réaliser une boucle sans utiliser for ou while.
Application 1 : Exemple de fonctions récursives
1) Recopier et testez la fonction prix(n) précédente.
Remarque : Vous pouvez aussi la tester à l'aide de https://pythontutor.com/
On considère la fonction suivante :
def fct(L, n = 0):
if n == len(L):
return 0
else:
return L[n] + fct(L, n+1)
2) Cette fonction est-elle récursive ? Justifier.
1) Que renvoie l'appel fct([1, 7, 3, 2]) ? Représenter les états successifs de la pile d'exécution lors
des appels récursifs (phases de descente et de remontée).
3) Quelle est l'efficacité temporelle de cette fonction ?
4) Pour chacune des fonctions suivantes, donner la valeur renvoyée lors de l'appel fct(5). Donner
également l'efficacité temporelle de chaque fonction.
a) def fct(n):
if n == 1:
return 1
else:
return 1 + fct(n - 1)
b) def fct(n):
if n <= 0:
return 1
else:
return n + fct(n//2)
- page 2 -
II- Résoudre un problème à l'aide d'une fonction récursive
1) Méthode générale pour définir une fonction récursive
Les fonctions récursives sont utiles lorsqu'on veut résoudre un problème en se basant sur la connaissance des
relations permettant de passer d'un état à l'autre : construction et sortie d'un labyrinthe, stratégie gagnante de
certains jeux (Hanoï, sudoku, mots croisés, …), backtracking, parcourt d'une arborescence, etc…
Exemple détaillé : On souhaite écrire une fonction récursive somme(n) renvoyant la somme des entiers de 0 à 𝑛.
Par exemple 𝑠𝑜𝑚𝑚𝑒(4) = 0 + 1 + 2 + 3 + 4 = 10
Pour écrire cette fonction, il faut se poser 2 questions :
• Quel est le cas de base ?
Autrement dit, quelle est la première valeur de 𝑛 pour laquelle on connaît la valeur de 𝐬𝐨𝐦𝐦𝐞(𝐧) ?
On remarque que si n = 0 alors la somme vaut 0. C'est le cas de base.
• Quel lien y a-t-il entre somme(n) et un autre rang de la fonction, par exemple somme(n-1) ?
Cela revient à chercher comment on passe de 𝑠𝑜𝑚𝑚𝑒(𝑛 − 1) à 𝑠𝑜𝑚𝑚𝑒(𝑛).
Pour le trouver, on peut par exemple remarque que :
𝑠𝑜𝑚𝑚𝑒(3) = 0 + 1 + 2 + 3
et s𝑜𝑚𝑚𝑒(4) = 0 + 1 + 2 + 3 + 4
Donc 𝑠𝑜𝑚𝑚𝑒(4) = 𝑠𝑜𝑚𝑚𝑒(3) + 4
En le généralisant, on obtient la relation de récurrence : somme(n) = somme(n-1) + n
Application 2 : Ecriture d'une fonction récursive
2) Ecrire la fonction récursive somme(n) précédente calculant la somme des entiers de 0 à 𝑛.
3) Représenter au brouillon les états successifs de la pile d'exécution lors des appels récursifs.
2) Entrainement et algorithmes classiques
Application 3 : Factorielle d'un nombre
On souhaite calculer le produit des entiers jusqu'à un entier 𝑛 (strictement positif) : 1 × 2 × 3 × … × 𝑛
Ce produit s'appelle la factorielle de 𝑛 et on le note également 𝑛!
1) Calculer manuellement 5!
2) Proposer une fonction factorielle(n) permettant de calculer 𝑛! de manière récursive.
Remarque : par convention mathématique, 0! vaut 1
Application 4 : Recherche d'un élément dans une liste
On considère une liste d'entiers, par exemple L = [1,7,6,5,3,2]
1) Ecrire une fonction recherche(L, x, n=0) effectuant la recherche séquentielle de la valeur x dans
la liste L. L'appel recherche(L, 5) renvoie ainsi True et recherche(L, 8) renvoie False.
2) Quelle est l'efficacité temporelle de cette fonction ?
Application 5 : Exponentiation rapide
On souhaite calculer 𝑥 𝑛 réalisant le produit 𝑥 × 𝑥 × 𝑥 × … × 𝑥
1) Proposer une fonction puissance(x, n) calculant 𝑥 𝑛 de manière récursive, pour 𝑛 ≥ 0.
On rappelle que, par convention, 𝑥 0 = 1.
Une autre définition possible (certes moins intuitive…) de la fonction puissance est la suivante :
1 𝑠𝑖 𝑛 = 0
𝑛/2
𝑛
𝑥 ={ (𝑥 )² 𝑠𝑖 𝑛 𝑒𝑠𝑡 𝑝𝑎𝑖𝑟 𝑒𝑡 𝑛 ≥ 1
𝑥 × (𝑥 (𝑛−1)/2 )² 𝑠𝑖 𝑛 𝑒𝑠𝑡 𝑖𝑚𝑝𝑎𝑖𝑟 𝑒𝑡 𝑛 ≥ 1
2) Proposer une fonction expo(x, n) calculant 𝑥 𝑛 par la méthode d'exponentiation rapide ci-dessus.
3) Commenter les efficacités de ces 2 fonctions.
- page 3 -
III- Le problème de l'efficacité spatiale
1) Mise en évidence du problème
Puisque la récursivité place en mémoire dans une pile d'exécution les calculs qui ne peuvent pas être résolus (en
attendant d'atteindre le cas de base), la récursivité nécessite généralement davantage de place en mémoire que
les algorithmes itératifs classiques que vous avez rencontrés jusqu'à présent.
Cette perte d'efficacité spatiale peut parfois être problématique.
Application 7 : La suite de Fibonacci
La suite de Fibonacci est une suite célèbre qui se construit de la façon suivante : un terme de la suite est la
somme des 2 précédents, les 2 premiers termes de la suite valant 0 et 1.
1) Que vaut 𝐹8 ?
2) Ecrire une fonction récursive fibo(n) prenant en paramètre un entier n et renvoyant la valeur de 𝐹𝑛
Cette fonction récursive possèdera 2 cas de base, un pour n == 0 et un pour n == 1, car le calcul de
fibo(n) dépendra de fibo(n-1) et fibo(n-2).
3) Vérifiez votre fonction pour fibo(4) et représentez au brouillon les états successifs de la pile
d'exécution. Que donnerait cette pile avec fibo(5) ?
Testez ensuite fibo(42). Qu’observez-vous et comment le justifiez-vous ?
2) Approche par programmation dynamique
Une façon de régler ce problème et d'optimiser l'algorithme est d'utiliser une approche qu'on appelle la
programmation dynamique.
La technique de programmation dynamique consiste à stocker dans un tableau intermédiaire les résultats de
calculs afin d'éviter d'avoir à les refaire inutilement.
On utilise généralement cette technique de programmation lorsqu'une fonction nécessite plusieurs fois les
résultats d'un même calcul.
Dans le cas de Fibonacci par exemple, on pourrait stocker dans un dictionnaire ou dans une liste les valeurs de la
suite correspondant à chaque terme :
{0:0, 1:1, 2:1, 3:2, 4:3, 5:5, 6:8, 7:13, … } ou [0, 1, 1, 2, 3, 5, 8, 13, …]
La fonction fibonacci pourrait alors être optimisée de la façon suivante par programmation dynamique (cette façon
de procéder s'appelle la mémoïsation ou programmation dynamique top-down) :
def fibodyn(n, memo = {0:0, 1:1}):
if n in memo:
return memo[n]
else:
memo[n] = fibodyn(n-1) + fibodyn(n-2)
return memo[n]
Application 8 : Programmation dynamique
1) Recopier et tester la fonction fibodyn utilisant la technique de programmation dynamique.
Testez cette fonction avec fibodyn(42) et expliquez les raisons de cette amélioration.
2) Modifiez la fonction fibodyn(n, memo={0:0, 1:1}) en la débutant comme suit :
def fibodyn2(n, memo = {0:0, 1:1}):
if n not in memo:
… à compléter …
3) Rédigez une fonction fibodyn3 utilisant une liste à la place d'un dictionnaire.
Pour comprendre la récursivité, il faut d'abord comprendre la récursivité.
- page 4 -
