Terminale, Spécialité Numérique et Sciences Informatiques

La récursivité
éléments de cours

1 Notion de récursivité

1.1 Dénition
Une fonction f est dite  récursive  si la fonction f, lors de son
exécution, fait un appel à ... elle même.
Oui, c'est un peu curieux, comme si les pompiers appelaient les pompiers ! Mais nous allons voir que
nalement, cela peut devenir assez naturel.

1.2 Premier exemple.

Ainsi, imaginons une fonction trier(a, b, c) qui renvoie la liste des trois entiers a, b et c triés dans
l'ordre croissant. Nous allons ici utiliser un algorithme de tri très simpliste.
1 def t r i e r ( a , b , c ) :
2 # cas où a <= b
3 i f a <= b <= c :
4 return [a,b, c ]
5 i f a <= c <= b :
6 return [a,c ,b]
print ( t r i e r (18 , 9 , 2 7 ) ) 7 i f c <= a <= b :
[ 9 , 18 , 2 7 ]
8 return [c ,a,b]
9 # L ' autre cas
10 i f b <= a <= c :
11 return [b,a, c ]
12 i f b <= c <= a :
13 return [b,c ,a]
14 i f c <= b <= a :
15 return [c ,b,a]
Mais, les lignes 10-15 refont exactement ce que font les lignes 3-8 sauf que a et b sont échangées. Donc les
lignes 10-15 sont équivalentes à un appel trier(b, a, c) de trier entre les lignes 3 et 8. D'où le code suivant :
1 def t r i e r ( a , b , c ) :
2 i f a <= b <= c :
3 return [ a , b , c ]
4 i f a <= c <= b :
5 return [ a , c , b ]
6 i f c <= a <= b :
7 return [ c , a , b ]
8 return t r i e r ( b , a , c )

I Si a ≤ b alors l'appel trier(a, b, c) exécute une des instructions lignes 3, 5 ou 7 ce qui renvoie la liste
ordonnée.
I Sinon, le code passe à la ligne 8 et la fonction trier est appelée en échangeant les arguments a et b en sorte
qu'à l'appel suivant, une des lignes 3, 5 ou 7 est exécutée et on obtient bien la liste triée.
La fonction trier est une fonction qui s'appelle elle-même (à la ligne 8) : c'est une fonction récursive, ce n'est pas
plus compliqué que ça.

2.2 Structures de données Page 1/4

J.Devalette, d'après P.Ortiz
 Terminale, Spécialité Numérique et Sciences Informatiques
2 Exécution d'une fonction récursive

2.1 Un exemple typique de fonction récursive

L'exemple du paragraphe précédent n'est pas typique d'une fonction récursive car lorsque la fonction s'exé-
cute, il n'y a qu'un seul appel récursif.
Voici un exemple plus représentatif. On va écrire une fonction récursive afficherAnnees(debut, fin) qui
ache, une par une, toutes les années depuis l'année debut jusqu'à l'année n.
Si debut ≤ f in , l'appel afficherAnnees(debut, fin) est équivalent aux deux actions suivantes :
I acher l'année debut
I acher toutes les années de l'année debut + 1 à l'année n.
Or, la 2e action, par dénition de la fonction afficherAnnees, peut être accomplie par un appel de la
fonction afficherAnnees(debut + 1, fin). On a donc le code pour une fonction récursive :
a f f i c h e r A n n e e s ( 2 0 2 0 , 2024)
2020 1 def a f f i c h e r A n n e e s ( debut , f i n ) :
2021 2 i f debut <= f i n :
2022 3 print ( debut )
2023 4 a f f i c h e r A n n e e s ( debut +1, f i n )
2024
Noter que lorsque la condition debut ≤ f in devient fausse, la fonction n'ache rien et l'appel est terminé.

2.2 La pile d'appel

Enrichissons légèrement le code de la fonction afficherAnnees :
a f f i c h e r A n n e e s ( 2 0 2 0 , 2022)
Bonjour 2020 1 def a f f i c h e r A n n e e s ( debut , f i n ) :
Bonjour 2021 2 i f debut <= f i n :
Bonjour 2022 3 print ( " Bonjour " , debut )
Bye bye 2022 4 a f f i c h e r A n n e e s ( debut +1, f i n )
Bye bye 2021 5 print ( "Bye bye " , debut )
Bye bye 2020
Pour bien comprendre le ux d'exécution de ce code, vous pouvez vous rendre sur le site Pythontutor.
Il propose un outil en ligne permettant de visualiser l'exécution de votre code et l'état de la mémoire pendant
l'exécution. Cet outil est pratique pour pouvoir observer la pile des appels d'une fonction récursive.
I se rendre sur cette page
I coller votre code dans la zone de texte
I cliquer sur le bouton Visualize Execution.
Observons l'exécution de ce code :
I Le premier appel afficherAnnees(2020, 2022) à la ligne 3 va provoquer l'achage de
'Bonjour 2020' et provoquer l'appel récursif afficherAnnees(2021, 2022) à la ligne 4.
I Les deux appels suivants afficherAnnees(2021 2022) et afficherAnnees(2022, 2022)
provoquent l'achage de 'Bonjour 2021' et 'Bonjour 2022'.
I Noter que le code à la ligne 5 n'a toujours pas été exécuté.
I Après l'appel afficherAnnees(2022, 2022) l'appel afficherAnnees(2023, 2022) est lancé ;
la pile des appels contient alors 4 appels qui s'empilent.
I Désormais, les appels vont dépiler puisque 2023 > 2022.
I L'appel afficherAnnees(2023, 2022) ne provoque aucun eet mais, en se terminant, il va
débloquer l'appel afficherAnnees(2022, 2022) ce qui permet l'achage de Bye bye 2022.
La pile des appels diminue d'une unité.
I Chaque n d'appel provoque alors le déblocage du code de la ligne 4 puis l'achage Bye
bye.
I A la n, la pile d'appels est vide.

2.2 Structures de données Page 2/4

J.Devalette, d'après P.Ortiz
 Terminale, Spécialité Numérique et Sciences Informatiques
2.3 Limite des appels récursifs
Il existe de nombreuses situations algorithmiques où il est ecace d'utiliser une fonction récursive. Toutefois,
les appels sont eectués sur une zone de mémoire plutôt limitée (dite stack alias la pile) et donc la pile d'appels
ne doit pas dépasser une certaine limite. Par défaut, elle est de 1000 dans l'implémentation courante de Python.
Sinon, on obtient une erreur :
1 def f ( n ) :
print ( f ( 5 0 0 0 ) ) 2 # Calcule 1+2+...+n
RecursionError :
3 i f n==0:
maximum r e c u r s i o n depth exceeded in comparison
4 return 0
5 else :
6 return n+f ( n −1)
Le plafond de 1000 peut varier selon les réglages de Python. Par exemple, avec la version Jupyter- Notebook
d'Anaconda, le plafond semble plutôt autour de 3000 appels récursifs. En Python, il est possible de modier le
plafond du nombre d'appels :

1 import s y s
2 sys . s e t r e c u r s i o n l i m i t (5000)

3 Ecrire un algorithme récursif

3.1 Un peu de méthode

Pour écrire un algorithme récursif résolvant un problème X appliqué à un objet N, on dégage
les deux éléments suivants :
I le sous-problème : on identie le même problème que le problème X mais appliqué à un
objet M de  taille  inférieure et dont la résolution permet de résoudre le problème
X appliqué à l'objet N
I le cas de base : on isole le cas du problème X appliqué à un objet de taille telle que le
problème pour X ne peut être ramené à un sous problème ; il s'agit en quelque sorte
d'un cas irréductible qui représente la condition d'arrêt.

3.2 Application à un exemple simple

Soit la fonction f telle que, pour tout entier n ≥ 1 on ait f (n) = 1 + 2 + .... + n, somme des entiers entre 1
et n inclus. Par exemple,
I f (3) = 1 + 2 + 3 = 6
I f (4) = 1 + 2 + 3 + 4 = 10
I f (10) = 1 + 2 + 3 + ... + 9 + 10 = 55
On va implémenter la fonction f dans une version récursive. La construction algorithmique de f est basée sur
l'observation suivante : pour connaître, par exemple, la somme S des entiers de 1 à 4, il sut de connaître la somme
T des entiers de 1 à 3 et dans ce cas S = T + 4. Autrement dit
I f (4) = f (3) + 4
I f (n) = f (n − 1) + n
Le problème X est de calculer la somme S des n premiers entiers et l'objet N est l'entier strictement positif
n ; on se rend compte que pour connaître S, il sut de savoir résoudre le même problème mais pour un objet plus
petit, à savoir n − 1 puisque si l'on connaît la somme T des n − 1 premiers entiers alors S = T + n.
Cependant, la règle précédente ne s'applique que si on peut eectivement décomposer le problème ce qui
suppose que n vaut au moins 1 et ce qui fournit le cas de base.
Le problème de la terminaison de la récursion doit être examiné, même s'il est parfois délicat de la prouver,
elle nécessite souvent de raisonner par récurrence voire par induction.
Pour la fonction f , le code Python peut donc s'écrire :

2.2 Structures de données Page 3/4

J.Devalette, d'après P.Ortiz
 Terminale, Spécialité Numérique et Sciences Informatiques
1 def f ( n ) :
2 # Calcule 1+2+...+n
3 i f n==0:
4 return 0
5 else :
6 return n+f ( n −1)

3.3 Le saviez-vous ?
Dans certains environnements, l'usage de récursivité n'est pas permis.
. Dans le secteur du logiciel embarqué dans des véhicules (terrestres, aériens), certains principes d'implémenta-
tion d'unités logicielles découragent explicitement le recours à toute forme de récursion (directe ou indirecte),
cf. le standard ISO 26262, ou encore le standard MISRA pour le langage C ainsi que la norme JSF-AV
(avionique en C++).
. Les standards de codage de la NASA recommandent d'éviter toute forme de récursion, cela fait partie de la
règle n°1, cf. The Power of Ten (pdf).

4 Exercices

1. Dis  Bonjour !  : Écrire une fonction récursive bonjour(n) qui ache n fois le message Bonjour!.

2. Conversion en base b : Soit à déterminer la liste des chires de la représentation en base b d'un entier n.
Par exemple, si n = 13 et b = 2 alors les chires de la représen-
tation de n en base b sont les éléments de la liste [1, 1, 0, 1]
puisque 13 = 8 + 4 + 0 + 1. Autre exemple et qui permet de mieux
comprendre : la liste des chires en base 10 de l'entier 2038 est
[2, 0, 3, 8].
On observe alors que le reste r n'est autre que le dernier chire de
n et que le quotient q n'est autre que l'entier n privé de son dernier
chire. On peut donc reconstituer la liste des chires de n à partir
de celle de q et de celle de r. Dans notre exemple, et avec la syntaxe
Python des listes, on a [2, 0, 3, 8] = [2, 0, 3] + [8].
Complétez les lignes 3 et 4 du code ci-dessous avec le cas de base (condition d'arrêt)

1 def c h i f f r e s ( n , b ) :
2 # Manque le cas de base
3 .........
4 ..........
5 q= n // b
6 r = n % b
7 return c h i f f r e s ( q , b ) + [ r ]

5 Exercices Complémentaires

Vous trouverez tous les exercices complémentaires à rendre dans les notebooks :
. T2.2.1 Applications de la récursivité.
. T2.2.2 Pour aller plus loin avec la récursivité

2.2 Structures de données Page 4/4

J.Devalette, d'après P.Ortiz