Recursivité
Contenus : Récursivité.
Capacités attendues : Écrire un programme récursif. Analyser le fonctionnement d’un programme récursif.
Commentaires : Des exemples relevant de domaines variés sont à privilégier.
Logiciel nécessaire pour l'activité : Python 3 : Spyder, IDLE ...
Prérequis : les activités suivantes
- Programmation : programmation itérative - boucles,
A RENDRE ✎ :
1 - Définition
-
Larousse :
-
Propriété que possède une règle ou un élément constituant de pouvoir se répéter de manière théoriquement indéfinie. (C’est une propriété essentielle des règles d’une grammaire générative, celle qui permet d’engendrer un nombre infini de phrases.)
Qualité d’un programme informatique récursif.
Théorie destinée à fournir un cadre rigoureux à l'étude des notions intuitives de calculabilité et de décidabilité effectives. (Church a montré [1936] que la récursivité est l'équivalent mathématique de la calculabilité effective : la fonction récursive est une fonction rigoureusement calculable.)
-
récursif :
Se dit d’une règle ou d’un élément doués de récursivité. Se dit d’un programme informatique organisé de manière telle qu’il puisse se rappeler lui-même, c’est-à-dire demander sa propre exécution au cours de son déroulement.
Avec au passage, un bel exemple de récursivité (croisée).
-
-
La récursivité est une démarche qui fait référence à l’objet même de la démarche à un moment du processus. En d’autres termes, c’est une démarche dont la description mène à la répétition d’une même règle. Ainsi, les cas suivants constituent des cas concrets de récursivité :
- décrire un processus dépendant de données en faisant appel à ce même processus sur d’autres données plus « simples » ;
- montrer une image contenant des images similaires ;
- définir un concept en invoquant le même concept ;
- écrire un algorithme qui s’invoque lui-même ;
- définir une structure à partir de l’une au moins de ses sous-structures.
2 - Exemples
processus récursif
- Calcul de la fonction dérivée d’une fonction dérivable
Entrée : f (une fonction dérivable) - Sortie : f’ (la fonction dérivée)
derivee(f) =
si f est une fonction élémentaire de base
renvoyer sa dérivée
sinon si f == u+v
renvoyer derivee(u) + derivee(v)
sinon si f == u × v
renvoyer derivee(u)×v + u×derivee(v)
sinon si …
- Production de fractales : le flocon de Von Koch
On dispose de la primitive tracer(l) qui permet de tracer un segment de longueur l.
Le processus de tracé d’un segment de von koch de taille l à l’ordre n est :
vonkoch(l,n)
-
si n = 1, tracer(l)
-
sinon
- vonkoch(l/3, n-1)
- tourner à gauche de 60°
- vonkoch(l/3, n-1)
- tourner à droite de 120°
- vonkoch(l/3, n-1)
- tourner à gauche de 60°
- vonkoch(l/3, n-1)
Le flocon est obtenu en traçant 3 segments de von koch séparés par des rotations à droite de 120°.
NB Se réalise très bien avec la tortue (module turtle
), tracer(l) = forward(l)
et les fonctions right
et left
permettent les rotations
Images
- Print gallery M.C.Escher (mise en abime)
- La vache qui rit (mise en abime)
- Pochette Ummagumma de Pink Floyd
Sigles
C'est sigles sont auto-référentiels, ils font appel à la récursivité et plus précisément à l'auto-référence
- VISA : VISA International Service Association
- GNU : GNU is Not Unix
- WINE : Wine Is Not an Emulator
- Bing : Bing is not Google (non officiel)
- LAME : Lame Ain’t an MP3 Encoder
Grammaire
Un groupe nominal est composé d’un nom ou d’un nom et son complément. Le complément d’un nom est soit un adjectif, soit un adverbe, soit un groupe nominal. (très approximativement)
groupe_nominal ::= nom
| nom complement
complement ::= adjectif
| adverbe
| groupe_nominal
Algorithme récursif
Le tri rapide
listes, arbresStructures récursives
3 - Fonctionnement par un exemple
En classe de première, de nombreux programmes sont écrits avec des boucles et des affectations.
La notion de fonction permet en particulier d'éviter de réécrireun code similaireà plusieurs endroits d'un programme.
Le style de programmation est :
- impétatif, les séquences d'instructionssonr exécutées l'une après l'autre;
- itératif, des instructions sont exécutéesdans des boucles
while
oufor
Différents styles de programmations seront présentés dans un prochain chapitre.
Définitions
- Une fonction est dite récursive si elle s'appelle elle même.
- De manière générale, un sous programme est dit récursif s'il s'appelle lui même.
Fonction récursive
Nous parlons alors d'appel récursif.
Exemple : la somme des n premiers entiers
- Pour définir la somme des n premiers entiers, on a l’habitude d’écrire la formule suivante :
0 + 1 + 2 + ... + n
01° Ecrire, en Python, une fonction somme(n)
qui calcule la somme des n premiers entiers naturels.
- En utilisant une boucle
for
- En utilisant une boucle
while
- Autre méthode
Il existe en effet une autre manière d’aborder ce problème. Il s’agit de définir une fonction mathématique
somme(n)
qui, pour tout entier naturel n, donne la somme des n premiers entiers de la manière suivante :Cette définition nous indique ce que vaut
somme(n)
pour un entier n quelconque,selon que n soit égal à 0 ou strictement positif.Ainsi, pour n = 0,la valeur de
somme(0)
est simplement0
.
Dans le cas où n est strictement positif, la valeur desomme(n)
estn + somme(n − 1)
.- Par exemple
voici ci-dessous les valeurs de
somme(n)
, pour n valant 0, 1, 2 et 3.>Comme on peut le voir, la définition de
somme(n)
dépend de la valeur desomme(n − 1)
.
Il s’agit là d’une définition récursive, c’est-à-dire d’une définition de fonction qui fait appel à elle-même.
Ainsi, pour connaître la valeur desomme(n)
, il faut connaître la valeur desomme(n − 1)
, donc connaître la valeur desomme(n−2)
, etc.
Ceci jusqu’à la valeur desomme(0)
qui ne dépend de rien et vaut0
.La valeur de somme(n) s’obtient en ajoutant toutes ces valeurs.
- Principe de la recursivité
- il faut au moins une situation qui ne consiste pas en un appel récursif.
- chaque appel récursif doit se faire avec des données qui permettent de se rapprocher d’une situation de terminaison.
L’intérêt de cette définition récursive de la fonction somme(n)
est qu’elle est directement calculable, c’est-à-dire exécutable par un ordinateur.
En particulier, cette définition est directement programmable en Python, comme le montre le code ci-dessous:
def somme(n):
if n == 0:
return 0
else:
return n + somme(n-1)
L’analyse par cas de la définition récursive est ici réalisée par une instruction conditionnelle pour tester si l’argument n est égal à 0.
Si c’est le cas, la fonction renvoie la valeur 0
, sinon elle renvoie la somme n + somme(n - 1)
.
Cet appel à somme(n - 1)
dans le corps de la fonction 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 de toute fonction qui contient un appel récursif que c’est une fonction récursive.
- Exemple pour n = 3
l’évaluation de l’appel à somme(3)
peut se représenter de la manière suivante

où on indique uniquement pour chaque appel à somme(n)
l’instruction qui est exécutée après le test n == 0
de la conditionnelle.
Cette manière de représenter l’exécution d’un programme en indiquant les différents appels effectués est appelée arbre d’appels.
Ainsi, pour calculer la valeur renvoyée par somme(3)
, il faut tout d’abordappeler somme(2)
.
Cet appel va lui-même déclencher un appel à somme(1),qui à son tour nécessite un appel à somme(0).
Ce dernier appel se termine directement en renvoyant la valeur0
.
Le calcul de somme(3)
se fait donc « à rebours ».
Une fois que l’appel à somme(0)
est terminé, c’est-à-dire que la valeur 0 a été renvoyée,
l’arbre d’appels a la forme suivante, où l’appel à somme(0)
a été remplacé par 0
dans l’expression return 1 + somme(0)
.

À cet instant, l’appel à somme(1)
peut alors se terminer et renvoyer le résultat de la somme 1 + 0
.
L’arbre d’appels est alors le suivant.

Enfin, l’appel à somme(2)
peut lui-même renvoyer la valeur 2 + 1
comme résultat,
ce qui permet à somme(3)
de se terminer en renvoyant le résultat de 3 + 3
.

On obtient bien au final la valeur 6
attendue
Eléments Caractéristiques
if n == 0:
return 0
Cette situation est appelée situation de terminaison ou situation d’arrêt ou cas d’arrêt ou cas de base.
return n + somme(n-1)
Il faut s’assurer que la situation de terminaison est atteinte après un nombre fini d’appels récursifs.
4 - Aures Exemples
Exemple 1 : La fonction Factorielle
la fonction factorielle est définie, pour tout entier naturel n par (noté : n!) :
- 0! = 1
- n! = n x (n-1)! si n > 1
Principe :
5! = 5 x 4!
= 5 x 4 x 3!
= 5 x 4 x 3 x 2!
= 5 x 4 x 3 x 2 x 1!
= 5 x 4 x 3 x 2 x 1 x 0!
= 5 x 4 x 3 x 2 x 1 x 1
= 120
Programmation
def fact(n):
if n <= 1:
return 1
else:
return n * fact(n-1)
>>> fact(5)
120
Déroulement de l’exécution
Mise en évidence :
On utilise une application en ligne PythonTutor
Exemple 2 : Calculer le nombre d’occurrences d’un caractère dans une chaîne
Il faut trouver un énoncé récursif de résolution du problème, c’est-à-dire un énoncé qui fasse référence au problème lui-même
- Le nombre d’occurrences de c dans s est 0 si s est vide.
- Si c est le premier caractère de s, on ajoute 1 au nombre d’occurrences de c dans les autres caractères de s.
- Sinon, il s’agit du nombre d’occurrences de c dans les autres caractères de s.
Énonce
Programmation
def occurrences(c,s):
if s == "":
return 0
elif c == s[0]:
return 1 + occurrences(c,s[1:])
else:
return occurrences(c,s[1:])
La terminaison se vérifie en considérant la suite des longueurs des chaînes passées en paramètre.
Déroulement de l’exécution
Mise en évidence :
On utilise une application en ligne PythonTutor
5 - Récursivité Terminale
Définition
Un algorithme récursif simple est terminal lorsque l’appel récursif est le dernier calcul effectué pour obtenir le résultat.
Il n’y a pas de “calcul en attente”.
L’avantage est qu’il n’y a rien à mémoriser dans la pile.
Ce n’est pas le cas des deux exemples précédents fact
et occurrences
.
Exemple d’algorithme récursif terminal
- Un caractère c est présent dans une chaîne s non vide, s’il est le premier caractère de s ou s’il est présent dans les autres caractères de s.
- Il n’est pas présent dans la chaîne vide.
Prédicat de présence d’un caractère dans une chaîne
Programmation
def est_present(c,s):
if s == '':
return False
elif c == s[0]:
return True
else:
return est_present(c,s[1:])
Déroulement de l’exécution
Mise en évidence :
On utilise une application en ligne PythonTutor.
Rendre terminal un algorithme récursif
- Méthode
On utilise un accumulateur, passé en paramètre, pour calculer le résultat au fur et à mesure des appels récursifs.
La valeur de retour du cas de base devient la valeur initiale de l’accumulateur et lors d’un appel récursif, le “calcul en attente” sert à calculer la valeur suivante de l’accumulateur.
Ainsi on obtient :
def fact_term(n, acc = 1):
if n <= 1:
return acc
else:
return fact_term(n-1, acc * n)
et
def occurrences_term(c,s, acc = 0):
if s == "":
return acc
elif c == s[0]:
return occurrences_term(c,s[1:], acc + 1)
else:
return occurrences_term(c,s[1:], acc)
Activité publiée le 20 08 2020
Dernière modification : 27 08 2020
Auteur : Andjekel