Numérique et Sciences Informatiques - Terminale

Récursivité

Cours

Capacités attendues
Écrire un programme récursif.
Analyser le fonctionnement d’un programme récursif.

Notions d’architecture des ordinateurs

Le cœur d’un ordinateur comprend essentiellement :
 Une Unité Centrale (UC) ou microprocesseur. C’est le cerveau de la machine
et il effectue tous les calculs. En revanche, il possède peu de mémoire et donc
il ne peut stocker que peu d’informations à la fois.
 Une mémoire vive (RAM = random access memory) qui contient tous les
programmes en cours d’exécution : système d’exploitation (Linux, OS X,
Windows), logiciel de traitement de texte, tableau , etc ...
 Une mémoire de masse : disque dur, clé USB, disque CD ou DVD. C’est à cet
emplacement que sont stockés les fichiers et programmes qui ne sont pas
exécutés.
La mémoire vive est organisée comme une série de tiroirs placés les uns sur les autres
(cases mémoires). Chaque tiroir est de taille fixe et peut contenir exactement 1 octet.

1
Numérique et Sciences Informatiques - Terminale

D’autre part, chaque case mémoire possède un numéro unique qui l’identifie
complètement : ce numéro constitue l’adresse du tiroir. La numérotation commence
toujours à 0 pour la première case, puis 1 pour la seconde, etc ..., jusqu’au numéro N
de la dernière case, qui en général est très élevé.
Chaque case est relié à l’Unité Centrale par une série de fils de connexions (qui sont
en fait gravés sur un circuit imprimé). L’ensemble de tous ces fils est appelé BUS de
transfert de données. Ainsi, à chaque instant, l’UC peut envoyer des données
informatiques vers chacune des cases de la RAM ou en recevoir de chacune d’entre
elles.

2
Numérique et Sciences Informatiques - Terminale

Introduction
Organisation de la mémoire
La mémoire (RAM) d'un ordinateur contient à la fois le programme à exécuter et les
données que ces programmes doivent manipuler.
La mémoire d'un ordinateur peut être vue comme un tableau de cases mémoires
élémentaires, appelées mot mémoire.
Chaque case possède une adresse unique à laquelle on se réfère pour accéder à son
contenu (en écriture ou en lecture).
Le tableau ci-dessous décris l'organisation de l'espace mémoire d'un programme actif,
plus généralement appelé processus, c'est-à-dire un programme en cours d’exécution.

Cet espace et découpé en quatre parties, on dit aussi segment de mémoire :

 Le segment de code :
 Contient les instructions du programme ;

 Le segment de données :
 Contient les données dont l'adresse (en mémoire) et la valeur sont
connues au moment de l'initialisation - on parle de données statiques ;

 Le segment de pile :
 Contient l'espace mémoire alloué dynamiquement par un programme ;

3
Numérique et Sciences Informatiques - Terminale

 Utilisée au moment de l'appel de fonctions d'un programme ;

 La gestion en pile libère la mémoire au moment où la fonction se
termine ;

 Le segment du tas :
 Zone mémoire qui contient toutes les données allouées
dynamiquement ;
 Durée de vie non liée à l'exécution des fonctions ;
 Dont le type impose qu'elle soit allouée dans cette zone mémoire -
exemple : taille peut évoluer (tableaux Python).

Exemple simple d’un appel de fonction (démo⏵)

Chaque appel de fonction bloque la fonction appelante et exécute la fonction fille.

4
Numérique et Sciences Informatiques - Terminale

5
Numérique et Sciences Informatiques - Terminale

Exemple sur la gestion du segment de pile

Considérons les deux fonctions suivantes en Python et observons la gestion de la pile

décrite lors de l'appel f(1, 5).

def g(x, y) :
return 100 + y

def f(x, y) :
z= x+y
u = g(x-1, y*2)
return z + u

La pile (A) représente l'environnement lors de l'appel à f(1, 5).

Les premières cases mémoires contiennent :
 Une sauvegarde des registres du microprocesseur (reg),
 Un espace pour la valeur de retour de la fonction (ret),
 Les valeurs des paramètres
 Un espace pour la variable locale (ne contient aucune valeur au départ).

La pile (B) représente l'environnement lors de l'appel g(x – 1 , y * 2).

Pour réaliser cet appel :
 Un nouvel environnement est alloué sur la pile ;
 Avec une sauvegarde des registres et les valeurs des arguments x (0) et y (10)
de g ;
 Se termine en renvoyant la valeur 100 + y qui est stockée dans son espace de
retour (ret).

La pile (C) montre enfin l'environnement de f(1, 5) après le retour de g0, 10).
 L'espace alloué pour l'appel à g a été supprimé de la pile ;
 La valeur de retour (110) a été récupérée et stockée dans la case mémoire de
la variable locale u et que la somme z + u (116) est stockée dans l'espace de
retour.

6
Numérique et Sciences Informatiques - Terminale

Activité : Exercice 1

7
Numérique et Sciences Informatiques - Terminale

Problématique
Supposons que vous fouillez dans le grenier de votre grand-mère et que vous
tombiez sur une mystérieuse valise verrouillée.

Votre grand-mère vous dit que la clé de la valise est probablement dans une certaine
boite.

Cette boite contient d’autres boites, avec plus de boites à intérieur de ces boites. La
clé est dans une boite quelque part. Quels sera votre algorithme pour rechercher la
clé ? Pensez à un algorithme avant de poursuivre votre lecture.

8
Numérique et Sciences Informatiques - Terminale

Voici une approche :

1. Faites une file de boites à parcourir.

2. Prenez une boite et regardez dedans.
3. Si vous trouvez une boite, ajoutez-la à la file pour la parcourir plus tard.
4. Si vous trouvez une clé, vous avez terminé !
5. Répétez.

Voici une approche alternative :

1. Regardez dans la boite.

2. Si vous trouvez une boite, passez à l’étape 1.
3. Si vous avez trouvez une clé, vous avez terminé !

9
Numérique et Sciences Informatiques - Terminale

Cas de base et cas récursif

Parce qu’une fonction récursive s’appelle elle-même, il est facile d’écrire une fonction
de manière incorrecte et de causer une boucle infinie. Par exemple, supposons que
vous vouliez écrire une fonction qui affiche un compte à rebours, comme ceci :
Ø 3... 2...1
Vous pouvez l’écrire de manière récursive, comme ceci :

Écrivez ce code et exécutez-le. Vous remarquerez un problème : cette fonction

s’exécutera indéfiniment !

Ø 3... 2...1..0...-1....-2...
(Appuyer sur Ctrl-C pour tuer votre script.)
Lorsque vous écrivez une fonction récursive, vous devez lui dire quand arrêter la
récursion. C’est pourquoi chaque fonction récursive a deux parties : le cas de base et
le cas récursif. Le cas récursif est lorsque la fonction s’appelle elle-même. Le cas de
base est lorsque la fonction ne s’appelle plus elle-même ... Donc elle n’entre pas dans
une boucle infinie.
Ajoutons un cas de base à la fonction de compte à rebours :

10
Numérique et Sciences Informatiques - Terminale

Maintenant, la fonction fonctionne comme prévu. Cela donne quelque chose comme
ça :

Exécution pas à pas du compte à rebours (Démo)

Schéma d’exécution (dans Thonny)

11
Numérique et Sciences Informatiques - Terminale

12
Numérique et Sciences Informatiques - Terminale

Le principe
On aborde dans ce chapitre la programmation à l'aide de fonctions récursives.
Une fonction récursive est une fonction qui s’appelle elle-même.
Il s'agit à la fois :
 D’un style de programmation
 D’une technique pour résoudre certains problèmes qu'il n'est parfois pas facile
de traiter en programmant uniquement avec des boucles.

La somme des n premiers entiers

Pour définir la somme des n premiers entiers, on a l’habitude d’écrire la formule :

Une solution :
 Utiliser une boucle for pour parcourir tous les entiers i entre 0 et n.

Activité : Coder la fonction somme(n) permettant de calculer la somme des

n premiers entiers, à l’aide d’une boucle for.

def somme(n) :

 On peut remarquer que ce code Python n’est pas directement lié à la formule
de départ.

13
Numérique et Sciences Informatiques - Terminale

Il existe une autre manière d’aborder ce problème :

 Définir la fonction récursive somme(n) qui, pour tout entier naturel n, donne la
somme des n premiers entiers de la manière suivante :

Activité :
1. Écrire la fonction récursive somme(n) qui calcule la somme des n premiers entiers.
2. Dessiner l’arbre d’appels de cette fonction pour l’appel somme(5).

def somme(n) :

L’organisation de la mémoire lors de l’appel à somme(5) peut être représentée par la

pile ci-dessous :

14
Numérique et Sciences Informatiques - Terminale

 Un nouvel environnement d’exécution va être alloué dans la pile pour chacun

de ces appels.
 Après le dernier appel, la pile contient les contextes d’exécution pour les six
appels à la fonction somme.
 Lors de l’exécution d’une fonction récursive, chaque appel récursif conduit à un
empilement du contexte dans la pile d’exécution.
 Lorsque la condition d’arrêt de la récursivité se produit : les différents contextes
sont progressivement dépilés pour poursuivre l’exécution de la fonction.

Il est cependant possible de modifier le plafond du nombre d’appels :

import sys
[Link](3500)

15
Numérique et Sciences Informatiques - Terminale

Les principes de la programmation récursive

La programmation récursive est une approche où une fonction s'appelle elle-même

pour résoudre un problème.
Elle est particulièrement utile pour résoudre des problèmes qui peuvent être
décomposés en sous-problèmes similaires.

Voici les grands principes de la programmation récursive :

1. Cas de Base (Condition d'arrêt)
· Définition : Le cas de base est la condition qui permet de mettre fin à la
récursion. C'est une situation où le problème est suffisamment simple pour être
résolu directement, sans appel récursif supplémentaire.
2. Appel Récursif
· Définition : Si le cas de base n'est pas satisfait, la fonction s'appelle elle-même
avec un sous-ensemble du problème initial. Cela crée une série d'appels
imbriqués jusqu'à ce que le cas de base soit atteint.
3. Décomposition du Problème
· Définition : Un problème complexe est décomposé en sous-problèmes plus
simples, souvent similaires au problème initial. Cette répétition de la
décomposition est essentielle pour la récursion.
4. Convergence
· Définition : Pour qu'une fonction récursive fonctionne correctement, chaque
appel récursif doit se rapprocher du cas de base. Cela garantit que la récursion
finira par s'arrêter.
5. Empilement des Appels (Stack)
· Définition : Chaque appel récursif est empilé dans une pile d'appels, qui est
gérée automatiquement par le système d'exécution du programme. Lorsque le
cas de base est atteint, les appels sont "désempilés" et les résultats sont
combinés pour produire la solution finale.

Activité : Exercices 2, 3, 4 et 5.

16
Numérique et Sciences Informatiques - Terminale

Exemple : Le calcul de la factorielle d'un nombre

Le calcul de la factorielle d'un nombre est une opération mathématique qui consiste à
multiplier ce nombre par tous les entiers positifs inférieurs ou égaux à lui. La factorielle
d'un nombre entier positif n est notée n!

Activité : 1. Déterminer la fonction permettant de calculer la factorielle d'un

nombre n de manière récursive.
2. Dessiner l’arbre d’appels de cette fonction pour l’appel factorielle(5).

def factorielle(n):

Activité : Exercices 6 , 7.

17
Numérique et Sciences Informatiques - Terminale

D’autres formes de récursivité

Formulations récursives
Prenons comme exemple l'opération de puissance n-ième d'un nombre x, c'est à dire
la multiplication répétée n fois de x avec lui-même, que l'on écrit habituellement de la
manière suivante, avec par convention, que la puissance de x pour n = 0 vaut 1 :
xn = x * …. * x
n fois
Pour écrire une version récursive de xn , on va définir une fonction puissance(x, n) en
commençant par chercher les cas de base à cette opération. Ici, le cas de base évident
est celui pour n=0. Pour définir la valeur de puissance(x,n) pour un entier n strictement
positif, on suppose que l'on connaît le résultat de X à la puissance n – 1, c’est à dire la
valeur de puissance(x, n-1). On obtient la définition suivante :

puissance(x,n) = 1 si n = 0,
x * puissance (x, n-1) si n > 0.

Activité : Déterminer la fonction puissance(x, n) pour un entier n

strictement positif de manière récursive.

def puissance(x, n):

18
Numérique et Sciences Informatiques - Terminale

Définitions récursives plus riches

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 « faciles », celui pour n = 0 mais également celui pour n =
1, avec puissance(x, 1) = x. Ce deuxième cas de base a l'avantage d'éviter de faire la
multiplication (inutile) x * 1 de la définition précédente. Ainsi on obtient la définition
suivante avec deux cas de base :

puissance(x,n) = 1 si n = 0,
x si n = 1,
x * puissance (x, n-1) si n > 1.

On pourrait continuer à ajouter des cas de base pour n = 2, n= 3, mais cela

n'apportera rien à la définition et cela ne réduirait pas le nombre de multiplications à
effectuer.

Double récursion
Les expressions qui définissent une fonction peuvent aussi dépendre de plusieurs
appels à la fonction en cours de définition. Par exemple, la fonction fibonacci(n), qui
doit son nom aux mathématiciens Leonardo Fibonacci, elle définit récursivement, pour
tout entier naturel n, de la manière suivante :

fibonacci(n) = 0 si n = 0,
1 si n = 1,
fibonacci(n-2) + fibonacci(n-1) si n > 1.

19
Numérique et Sciences Informatiques - Terminale

Activité : Ecrire le détail des calculs et des appels récursifs pour les
fonctions fibonacci suivantes :
fibonacci(0) =
fibonacci(1) =
fibonacci(2) =
fibonacci(3) =
fibonacci(4) =
fibonacci(5) =

Activité : Dessiner l’arbre d’appel fibonacci(5)

Activité : Déterminer la fonction fibonacci(x) de manière récursive.

20
Numérique et Sciences Informatiques - Terminale

Récursion imbriquée

Les occurrences de la fonction en cours de définition peuvent également être

imbriquées. Par exemple, la fonction f91(n) est définie avec deux occurrences
imbriquées, de la manière suivante :

f91(n) = n-10 si n > 100,

f91(f91(n+11)) si n <=100.

Activité : Déterminer la fonction f91de manière récursive.

def f91(n):

# Exemple de test
for i in range(90, 110):
print(f"f91({i}) = {f91(i)}")

21
Numérique et Sciences Informatiques - Terminale

Récursion mutuelle.
Il est également possible, et parfois nécessaire, de définir plusieurs fonctions
récursives en même temps, quand ces fonctions font référence les unes aux autres.
On parle alors de définitions récursives mutuelles.
Par exemple, les fonctions F(n) et M(n) ci-dessous, inventées par Douglas Hofstadter
sont définies par récursion mutuelle de la manière suivante :

Activité : Déterminer les fonctions hofstadter_female(n) et

hofstadter_male(n) de manière récursive.

def hofstadter_female(n):

def hofstadter_male(n):

Activité : Exercices 8,9,10,11 et 12.

22
Numérique et Sciences Informatiques - Terminale

Écriture d’une fonction récursive

Une fonction récursive simple s’écrit sous la forme :

Pour écrire une fonction récursive on :

– Détermine le type de données à renvoyer ;
– Détermine pour quelle(s) valeur(s) de l’argument le problème est résolu et on
écrit la condition d’arrêt ;
– Détermine de quelle manière la taille du problème est réduite (argument entier
qui décroît strictement, liste dont la taille diminue, etc.)
– Écrit l’appel récursif en prenant garde à ce que le type de données qu’il
renvoie soit cohérent avec celui renvoyé par la condition d’arrêt.

23
Numérique et Sciences Informatiques - Terminale

Limites de la programmation récursive

1. Consommation de mémoire (pile d'exécution)

Chaque appel récursif crée une nouvelle entrée dans la pile d'exécution. Cela peut
entraîner un dépassement de la pile (stack overflow) si la profondeur de la récursion
est trop importante.

2. Risque de boucles infinies

Si la condition de sortie (ou base) n'est pas correctement définie ou atteinte, la fonction
récursive peut se retrouver dans une boucle infinie, entraînant une consommation
excessive de mémoire.

3. Complexité en temps
Certaines fonctions récursives peuvent recalculer plusieurs fois les mêmes résultats,
ce qui peut causer une augmentation substantielle du temps d'exécution. Par exemple,
la récursion naïve pour le calcul des nombres de Fibonacci : des sous-problèmes sont
recalculés plusieurs fois.

4. Difficulté de compréhension
Pour certaines personnes, les programmes récursifs peuvent être plus difficiles à
comprendre et à déboguer.

5. Performances (surcharge des appels)

Les appels de fonctions récursives peuvent être moins efficaces que les boucles
itératives, car chaque appel de fonction ajoute une surcharge liée à la gestion de la
pile d'exécution (sauvegarde du contexte, allocation de la pile, etc.).

6. Optimisation limitée
Sans optimisation de récursion terminale, la gestion de la pile peut être coûteuse.

En conclusion, bien que la récursion puisse apporter des solutions élégantes et

concises pour certains problèmes, elle doit être utilisée avec précaution en raison de
ces inconvénients, notamment en ce qui concerne la gestion de la mémoire et la
performance.

Préparer une carte mentale de la leçon.

24