Récursivité
1
Récursivité
Table des matières
1 Introduction 3
2 Modèle d’exécution 5
3 Les formulations récursives 5
2
Récursivité
1 Introduction
On aborde dans ce chapitre la programmation à l’aide de fonctions récursives. Il s’agit d’un style de
programmation mais également d’une technique pour définir des concepts et résoudre certains problèmes.
Exercice 1
d e f somme ( n ) :
r=0
f o r i i n r a n g e ( n+1) :
r=r+i
return r
1. Que retourne somme(3) ? somme(4) ? somme(5) ? somme (n) ?
Comme on peut le voir dans cet exercice, le but de la fonction somme n’est pas intuitif. On ne voit
pas directement le lien de la fonction somme avec la formule 1 + 2 + 3 + . . . + n. Certains peuvent y voir
l’art subtil de la programmation, d’autres peuvent se demander s’il est possible de programmer une fonction
somme plus "simple" comme
(
0 si n = 0
somme(n) =
n + somme(n − 1) si n > 0
Ici, somme(0) vaut simplement 0. On peut avoir quelques exemples ici avec des valeurs n strictement
positives :
somme(1) = 1 + somme(0) = 1 + 0 = 1
somme(2) = 2 + somme(1) = 2 + 1 = 3
somme(3) = 3 + somme(2) = 3 + 3 = 6
Comme on peut le voir, la définition de somme(n) dépend de la valeur de somme(n-1). Il s’agit là
d’une définition récursive : c’est-à-dire d’une fonction qui fait appel à elle-même. Voici comment
implémenter une fonction récursive avec Python :
d e f somme ( n ) :
i f n == 0 :
return 0
else :
r e t u r n n+somme ( n −1)
Si n est strictement positive, la fonction renvoie la somme n + somme(n − 1). Cet appel à somme(n − 1)
est un appel récursif, c’est à dire un appel qui fait référence à la fonction que l’on est en train de définir.
On dit que les fonctions faisant un appel récursif que c’est une fonction récursive. On peut représenter les
différents appels avec un arbre d’appels. Par exemple, pour somme(3) :
3
Récursivité
somme (3) = return 3 + somme(2)
|
return 2 + somme(1)
|
return 1 +
somme (0)
|
return 0
Ainsi, pour calculer somme(3), celui-ci va faire appel à somme(2). Celui-ci va faire appel à somme(1) qui
lui même va faire appel à somme(0). Ce dernier appel va donner la valeur 0. Le calcul de somme(3) se fait
donc "à rebours".
somme (3) = return 3 + somme(2)
|
return 2 + somme(1)
|
return 1 +0
A cet instant, l’appel à somme(1) peut se terminer et renvoyer la valeur 1 + 0. L’arbre d’appels est alors :
somme (3) = return 3 + somme(2)
|
return 2 + 1
somme(2) renvoit donc la valeur 2 + 1, ce qui permet à somme(3) de renvoyer le résultat : 3 + 3 = 6.
Attention : Pour garantir la terminaison d’une fonction récursive, il faut qu’il y ait un ou plusieurs "cas
de base", c’est-à-dire des valeurs pour lesquelles l’execution de la fonction ne donnera pas lieu à un appel
récursif. Dans notre exemple, le cas de base est la valeur n = 0 avec somme(0) qui est nul.
Exercice 2
On note n! (se lit n factorielle) le nombre 1 × 2 × 3 × . . . × n. avec la convention 0! = 1.
1. Calculer 1 !, 2 !, 3 ! et 4 !
2. Exprimer n! en fonction de (n − 1)!.
3. Implémenter une fonction f act(n) de deux manières différentes (itérative et récursive).
Exercice 3
Cet exercice est à faire sur feuille. Il ne faut pas taper le code et observer les résultats mais les trouver
mentalement ou par calcul. On peut bien evidemment verifier les résultats à posteriori.
def f(a , b) :
" " " In : a et b sont des e n t i e r s s t r i c t e m e n t p o s i t i f s
Out : ? ? ? ? " " "
i f b==1:
return a
else :
r e t u r n a+f ( a , b −1)
1. Quel résultat retourne f (7, 9) ?
2. Que fait cette fonction pour a et b entiers quelconques ?
4
Récursivité
3. Justifier la bonne terminaison de cette fonction (On pourra comme avec les boucles while associer
un variant).
Exercice 4
xn = x |
×x× {z
. . . × x}. Implémenter une fonction puissance (x,n) qui retourne ce résultat de deux
n fois
manières différentes (itérative et récursive)
Exercice 5
Implémenter (sans boucles) une fonction récursive nb_ diviseurs(j,n) qui renvoie le nombre d’en-
tiers entre 1 et j qui divisent n
2 Modèle d’exécution
Une partie de l’espace mémoire d’un programme est organisé sous forme de pile (on verra cette structure
dans un chapitre ultérieur). Reprenons l’exemple de la puissance. Pour éxecuter puissance(7,3), on commence
par ajouter sur la pile un "frame" où n vaut 3 et x vaut 7. Puis lors du calcul de puissance(7,2), il faut ajouter
un second frame où x vaut toujours 7 et n vaut 2. On continue ainsi jusqu’à ce que n vaut 0. Puis on dépile
pour calculer toutes les valeurs des fonctions appelées :
x=7
x=7 n=0 x=7
x=7 n=1 x=7 n=1 x=7
x=7 n=2 x=7 n=1 x=7 n=2 x=7
n=3 x=7 n=2 x=7 n=2 x=7 n=3
n=3 x=7 n=2 x=7 n=3
n=3 x=7 n=3
n=3
Attention : Python limite le nombre d’appels récursifs à 1000. Si vous tentez d’en faire davantage,
l’interpréteur de Python va lever une exception RecursionError et afficher un message d’erreur.
Exercice 6
Executer la fonction f act(n) avec n = −2 (la version récursive). Que se passe-t-il ? Comment corriger
cette erreur ?
3 Les formulations récursives
Toute formulation récursive d’une fonction possède un cas de base et un cas récursif (comme somme(n) =
n + somme(n − 1)).
Ceci étant posé, une grande variété de formes est possible.
5
Récursivité
Cas de base multiples
La définition de la fonction puissance(x, n) n’est pas unique. On peut par exemple identifier deux cas
de base evident comme n = 0 mais également n = 1. On obtient ainsi :
1
si n = 0
puissance(x, n) = x si n = 1
x × puissance(x, n − 1) si n > 1
Cas récursifs multiples
Il est également possible de définir une fonction avec plusieurs cas récursifs. On peut, par exemple, définir
la fonction puissance(x, n) en distinguant deux cas récursifs selon la parité de n. En effet, si n est pair,
xn = (xn/2 )2 . Si n est impair, on a alors xn = x × (x(n−1)/2) )2 .
Exercice 7
1. Programmer la fonction puissance avec le cas récursif multiple.
2. Décrire l’arbre des appels et le comparer avec la fonction puissance implémentée à l’exercice 4.
Double récursion
La suite de Fibonacci doit son nom au mathématicien Leonardo Fibonacci et est définie par un+2 =
un+1 + un avec u0 = 0 et u1 = 1.
Exercice 8
1. Calculer les 6 premiers termes de cette suites.
2. Programmer une fonction récursive appelée Fibonacci(n) pour calculer le terme de rang n de la
suite
Récursion imbriquée
Comme l’indique le titre, les récursions peuvent être imbriqueés. Par exemple, la fonction f91 (n) que l’on
doit à John McCarthy est définie avec deux occurences imbriquées :
(
n − 10 si n > 100
f91 (n) =
f91 (f91 (n + 11)) sinon
Exercice 9
Calculer f91 (99)
Nous avons encore d’autres récursions comme les récursions mutuelles que nous n’allons pas décrire dans ce
cours.
Exercice 10 (Suite de Syracuse)
On définit une suite (un ) de la manière suivante :
• u0 = 1000
6
Récursivité
• si un = 1, alors la suite est finie et un est son dernier élément
un
• si un est pair, alors un+1 =
2
• si un est impair et distinct de 1, alors un+1 = 3un + 1
Écrire un programme qui affiche les termes de la suite (un ).
Exercice 11
Ecrire une fonction nombre_de_chiffres(n) qui prend un entier positif ou nul n en argument et
renvoie son nombre de chiffres. Par exemple, nombre_de_chiffres(758) renvoie 3.