Récursivité

I. Problèmes pratiques d’introduction :

 Découper une feuille A4 en 32 parties égales ?

1) Une première démarche serait de calculer la taille correspondante de la partie à découper 32 fois, de la dessiner
puis de découper.

2) Une seconde approche, convenant à ce cas concret (choix de 32), serait de couper la feuille en deux, puis de
recommencer avec chaque nouveau morceau.

 Des grands parents viennent de planter un arbre de 15cm dans le jardin pour leur petit fils de 10 ans. Le
vendeur leur a dit qu’il allait grandir de 30cm chaque année. Quelle sera sa taille lorsque le petit fils aura
20 ans ?

Plusieurs approches peuvent être envisagées afin de trouver le résultat. Une des approches pourrait être la suivante :

- La taille au bout de 10 ans est égale à la taille au bout de 9 ans + 30cm.

- La taille au bout de 9 ans est la taille au bout de 8 ans + 30 cm
- Etc…
- La taille au bout d’un an est la taille initiale + 30cm  Qui devient connue et qui permet alors de
« remonter » pour donner la réponse.

 Conversion en Binaire :

On divise le nombre par deux, on note son reste et on recommence la démarche avec le quotient jusqu’à ce que le
quotient soit égal à zéro.

 Les fractales :

…… Une fractale est un dessin / objet qui a une structure

similaire à toutes les échelles. Cela implique une définition de
type récursif : un objet fractal est un objet dont chaque élément
est aussi un objet fractal identique.
Quelques exemples :
Le flocon de Von Koch : il se construit de manière récursive :
On part d'un triangle équilatéral, on découpe chaque segment en
trois, on enlève le tiers médian que l'on remplace par les deux
côtés de même taille d'un triangle équilatéral vers l'extérieur.
Et on recommence jusqu'à l’infini.

La fougère de Barnsley : elle est construite à l’aide d’une suite

définie à l’aide de matrices (𝑈 = 𝐴. 𝑈 + 𝐵).

L’ensemble de Mandelbrot : il est défini à l’aide d’une suite de nombre complexe : 𝑧 =𝑧 +𝑐

Page 1 sur 6
 II. La récursivité :
En mathématiques, en informatique, en biologie, mais aussi dans notre quotidien, nous faisons souvent face à des
situations où un problème doit être résolu en utilisant une méthode de résolution qui est répétée plusieurs fois
exactement de la même manière.

De manière itérative, la méthode est appliquée par paliers de façon séquentielle, tandis que dans la récursivité, la
méthode s'appelle elle-même.

Voici de manière visuelle la différence d’exécution selon le mode itératif ou récursif (la méthode est ResoudrePbm) :

Mode Itératif Mode Récursif

ResoudrePbm ResoudrePbm
. Contexte exécution – appel 1
Contexte exécution –
Boucle for ou while ayant N-Itérations

appel 1 ResoudrePbm
Contexte exécution – appel 2
ResoudrePbm
ResoudrePbm
Contexte exécution –
appel 2
...
.... ...
.. ResoudrePbm
ResoudrePbm Contexte exécution –
appel N
Contexte exécution –
appel N

A chaque itération, ResoudrePbm est A chaque itération, ResoudrePbm n’est pas encore
terminée. Le contexte d’exécution est terminée. Elle se terminera par cascade lorsque la
réinitialisé à chaque Itération. dernière itération sera finalisée. Le contexte d’exécution
de chaque appel est conservé jusqu’au niveau le plus bas.

Ainsi la récursivité peut être imaginée comme les poupées russes (matriochkas) : la plus
grande est l’appel lors de la première itération, et la plus petite la dernière itération.
Cette image permet aussi d’appréhender deux notions fondamentales en récursivité :

- La résolution ne peut se faire qu’en connaissant la résolution du niveau

intérieur
- Le nombre de poupées est limité par leur taille, c’est identique avec un
processeur, il ne pourra pas dépasser un certain nombre d’appels (appelé taille de la pile : call stack en
anglais). En python, le maximum de profondeur d’appel (nbre d’itérations récursives) par défaut est de 1000.

1. Définition : une fonction récursive

Une fonction est dite récursive si dans son exécution elle s’appelle elle-même.

Il peut être également possible d’avoir deux fonctions (ou plus) qui s’appellent l’une l’autre, cette situation est
appelée : récursivité croisée.

2. Structure d’une fonction récursive

Toute fonction construite de manière récursive doit respecter une certaine structure. Elle contient deux
éléments obligatoires : l’un est primordial pour que les appels s’arrêtent et l’autre, pour que la fonction soit dite
récursive.

Page 2 sur 6
 La structure d’une Fonction Récursive, les éléments à prévoir lors de son écriture :

 Condition d’arrêt (obligatoire) : qui correspond au cas de base, c’est-à-dire le cas où il n’y a
plus besoin d’appeler la fonction.
 Ainsi, si valide, elle permet de sortir de la fonction (avec ou sans valeur retournée) sans
appeler une nouvelle fois la fonction

 Un traitement, optionnel car il est dépendant de ce que doit résoudre la fonction récursive

 Appel à elle-même (obligatoire) avec des valeurs de paramètres qui permettent d’obtenir, à
une certaine étape, la condition d’arrêt.

3. Intérêt des algorithmes récursifs

Deux intérêts qui se ressemblent dans le fond :

a. Décomposer une action répétitive en sous-actions « identiques » de plus petites tailles :

 Calculer un résultat, résoudre un problème, rechercher un élément dans un tableau trié,
trier un tableau, …
 Représenter des structures « fractales »
b. Explorer des solutions possibles (les coups possibles dans un jeu). Le fait de garder le contexte de
chaque appel, il est alors facile, au besoin, de revenir en arrière et ainsi d’évaluer les meilleures
combinaisons.
4. Les points de vigilances
 Toute problématique résolue de manière itérative peut être résolue aussi par une méthode récursive et
vice versa. La complexité d’un passage de l’un à l’autre est la gestion du contexte des variables
nécessaires à chacune des étapes. Cependant, le choix de la récursivité ne doit pas être systématique
même si elle peut paraître plus simple à son implémentation. Il est important d’évaluer ses bénéfices
d’un point de vue performance d’exécution : exemple factorielle, suite de Fibonacci, …
 La Condition d’arrêt : vérifier qu’à un certain moment, le cas de base est obtenu (sinon cela va
déclencher une erreur de pile (call stack))
 A chaque appel de la fonction, il faut s’assurer que les paramètres passés seront toujours dans le
domaine de définition de la fonction (exemple : une fonction racine carrée qui ne peut pas accepter une
valeur négative). Pour cela, deux propositions de démarche :
o Valider les paramètres lors de l’appel (utilisation de assert afin de provoquer une erreur précise)
o Mettre une condition d’arrêt qui englobe et élimine le cas (on travaille avec des entiers naturels,
et à un moment on peut passer à une valeur négative sans passer par 0. On envisagera donc une
condition d’arrêt qui peut englober ces cas : « <=0 » au lieu de « ==0 » par exemple)

III. Exemples d’application

1. Conversion en binaire d’un nombre décimal
Une des méthodes que nous avons vue en première est la méthode euclidienne. Rappelons-la:

1. On prend le nombre en base 10

2. On le divise par 2 et on note le reste de la division (donc soit 1 ou 0)
3. On reprend l’étape 1 avec le quotient obtenu jusqu’à ce que le quotient soit nul.

 La condition de base ou la condition d’arrêt sera donc : quotient égal à 0.

On remarque que si le quotient est égal à 0 on ne fait rien. Afin d’éliminer un appel inutile,
on peut dans ce cas choisir de s’arrêter au niveau précédent, lorsque le quotient = 1.
Dans ce cas, on retournera 1.
 Définissons maintenant la définition récursive :
nbreBinaire(q)=reste (q/2) concaténé à nbreBinaire(quotient (q/2))

Page 3 sur 6
 Nous obtenons alors l’algorithme suivant :
Fonction convertirEnNbreBinaire (nbre)
Si nbre = 0 alors retourner 0
Sinon
reste  reste de la division euclidienne de nbre par 2
quotient  quotient de la division euclidienne de nbre par 2
retourner reste concaténé à convertirEnNbreBinaire(quotient)

Voici deux exemples d’écriture en Python (identique en fonctionnement) :

def convertirEnNbreBinaire(nbre): def convertirEnNbreBinaire2(nbre):

if nbre == 1: # condition de base if nbre > 1:
return "1" return convertirEnNbreBinaire2(nbre // 2) + str(nbre % 2)
else: return "1" # condition de base
q = nbre // 2
r = nbre % 2
return convertirEnNbreBinaire(q) + str(r)

2. Exemple de l’arbre planté par les grands parents

L’arbre mesurant 15 cm au départ, grandit de 30cm chaque année. Quelle est sa taille 10 ans plus tard ?

L’approche itérative vue en première :

Fonction calculerTaille ( n )
t  15 Valeur de démarrage
répéter n fois : Répétition de la formule de calcul
t t + 30
retourner t Fin d’exécution avec la valeur de fin

L’approche récursive :
Fonction calculerTaille ( n ) Condition de base (condition de fin)
Si n = 0 alors retourner 15 Calcul de la valeur à l’aide de la formule
t  30 + calculerTaille(n-1) récursive : 30 + taille année précédente
retourner t Fin d’exécution de la fonction en cours en
retournant la valeur courante

3. Autres exemples :
a. Factoriel d’un nombre entier 𝒏, noté 𝒏!
La factorielle de 𝑛, 𝑛! = 𝑛 × (𝑛 − 1) × … × 1, peut-être implémentée en mode récursif :

- Condition de base : n = 1, la valeur est 1

- Définition récursive : 𝑛! = 𝑛 × (𝑛 − 1)!

La version itérative est bien plus performante que la version récursive (coût des appels des fonctions et de la gestion
des contextes des variables pour chaque appel)

b. Pgcd d’un nombre entier n non nul

Le calcul du PGCD de deux nombre (n, p) peut se faire en mode récursif selon :

- Condition d’arrêt : 𝑝 = 0, la valeur est n

- Définition récursive : PGCD(n,p) = PGCD(p, le reste de la division euclidienne de n par p (n%p))

Page 4 sur 6
 Exercices d’entrainements
Exercice 1 : L’arbre des grands-parents (Enoncé du cours)
1) Réaliser la fonction calculerTailleRecursif qui permet de calculer la taille de l’arbre. Le nombre d’années
sera entrée par l’utilisateur
2) Programmer une version itérative de cette situation : calculerTailleIteratif
3) Ajouter le code nécessaire afin de calculer le temps mis par chacune des fonctions et comparer les
résultats pour des nombres d’années différents.
Exercice 2 : Factoriel d’un nombre entier positif
1) Réaliser la fonction calculerFactRecursif qui calcule la factorielle d’un nombre entier positif entré par
l’utilisateur.
2) Réaliser la fonction calculerFactInteratif qui calcule la factorielle en mode itératif et comparer le temps
d’exécution des deux versions
Exercice 3 : Compte à rebours.
Ecrire une fonction récursive qui affiche le compte à rebours toutes les 20ms à partir d’un nombre entré par
l’utilisateur. NB : la fonction sleep(x) avec x en ms est une fonction de la bibliothèque time.
Exercice 4 : Palindrome.
Ecrire une fonction récursive qui vérifie si un mot est un palindrome. Ex : ressasser, stats, radar, abba, …
Exercice 5 : Que fait la fonction suivante :
def rFonction(x,n):
Reda propose la fonction suivante : que fait-elle ? if n == 0:
return 1
else:
return x * rFonction(x, n - 1)

Amina propose une seconde fonction qui a le même

objectif que la fonction qu’a proposée Reda : def aFonction(x,n):
if n == 0:

return 1
A votre avis, quel est l’intérêt de la version elif n == 1:
proposée par Amina ?
return x
else:
r = uneFonction(x, n // 2)
if n % 2 == 0:
return r * r
else:
return x * r * r
Exercice 5 : Suite de Syracuse :
Réaliser la fonction récursive qui permet d’afficher les valeurs successives d’une suite tant que les termes sont
supérieurs strictement à 1. La suite (𝑢 ) est définie par :

- 𝑢 est un entier quelconque supérieur à 1

, 𝑠𝑖 𝑢 𝑒𝑠𝑡 𝑝𝑎𝑖𝑟
- 𝑢 = sachant que
3 × 𝑢 + 1, 𝑠𝑖 𝑢 𝑒𝑠𝑡 𝑖𝑚𝑝𝑎𝑖𝑟
NB : Démontrer qu’une fonction récursive se termine bien peut être parfois très délicat, bien que dans les faits
elle se termine toujours. C’est justement le cas avec la conjecture de Syracuse, illustrée par cette suite, qui n’a
pas encore pu être démontrée à ce jour.
Exercice 6 : La suite de Fibonacci.
Ecrire une fonction récursive qui affiche les valeurs (termes) de la suite définie par :
𝑢 =𝑢 =1
𝑢 =𝑢 +𝑢
Ecrire la version itérative et comparer les temps d’exécution des deux versions.
Page 5 sur 6
Exercice 7 : Les carrés imbriqués

Ecrire une fonction récursive tracerCarre(n, x,y,c,d) qui trace, à l’aide de

Turtle, n carrés emboîtés.
Pour cela, on pourra utiliser une fonction avec les paramètres suivants :
- n : le nombre de carrés à tracer
- x et y : les coordonnées du départ du carré
- c : la longueur du coté
- et d : la distance entre 2 carrés ex : tracerCarre(15, 0,0,350, 10)
Exercice 8 : Le flocon de Von Koch

A l’aide de Turtle, réaliser un programme qui dessine un flocon de Von Koch.

Page 6 sur 6