Définition succincte
Une fonction sera dite programmée récursivement lorsqu'elle fait appel à elle-même dans le corps de sa définition.
Une fonction sera dite programmée récursivement lorsqu'elle fait appel à elle-même dans le corps de sa définition.
Le programme qui suit vous propose une fonction définie récursivement. Sa seule utilité est
de vous permettre, notamment à l'aide d'affichages, de comprendre le principe.
Un second exemple suivra, il présentera une légère modification
de ce premier programme, ce qui devrait vous permettre de mieux saisir le détail de fonctionnement des appels.
def d(n) :
if n==0 :
return 0
else :
print(n)
y=d(n-1)
return y
n=3
print( "Valeur de d({}) : {}.".format(n, d(n)) )
Réponse de python :
3 2 1 Valeur de d(3) : 0.
Schématisons le déroulement pour tenter de mieux saisir le fonctionnement.
Tout d'abord, la 'descente'.
Un premier appel de la fonction d avec l'argument 3 :
| Profondeur | Instructions | n=n1 | y1 | Affichage | Valeur retournée |
|---|---|---|---|---|---|
| 1 | Appel de la fonction d | 3 | - | ||
| 1 | (n==0) faux | 3 | - | ||
| 1 | print(n) | 3 | - | 3 | |
| 1 | y= | 3 | ▢ | ||
Lors de cette exécution de d(3), un appel à d avec l'argument 2 a lieu :
| Profondeur | Instructions | n1 | y1 | n=n2 | y2 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|
| 2 | d(n-1) | 3 | ▢ | 2 | - | ||
| 2 | (n==0) faux | 3 | ▢ | 2 | - | ||
| 2 | print(n) | 3 | ▢ | 2 | - | 2 | |
| 2 | y= | 3 | ▢ | 2 | ▢ | ||
Dans cette exécution de d(2), un appel à d avec l'argument 1 a lieu :
| Profondeur | Instructions | n1 | y1 | n2 | y2 | n=n3 | y3 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|---|---|
| 3 | d(n-1) | 3 | ▢ | 2 | ▢ | 1 | - | ||
| 3 | (n==0) faux | 3 | ▢ | 2 | ▢ | 1 | - | ||
| 3 | print(n) | 3 | ▢ | 2 | ▢ | 1 | - | 1 | |
| 3 | y= | 3 | ▢ | 2 | ▢ | 1 | ▢ | ||
Lors de l'exécution de d(1), un appel à d avec l'argument 0 a lieu :
| Profondeur | Instructions | n1 | y1 | n2 | y2 | n3 | y3 | n=n4 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|---|---|---|
| 4 | d(n-1) | 3 | ▢ | 2 | ▢ | 1 | ▢ | 0 | ||
| 4 | (n==0) vrai | 3 | ▢ | 2 | ▢ | 1 | ▢ | 0 | ||
| 4 | return 0 | 3 | ▢ | 2 | ▢ | 1 | ▢ | 0 | d(0)=0 |
Ensuite, on 'remonte' :
| Profondeur | Instructions | n1 | y1 | n2 | y2 | n3 | y3 | n4 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | sortie de 'd(0)' | 3 | ▢ | 2 | ▢ | 1 | ▢ | - | ||
| 3 | affectation y=d(n-1) | 3 | ▢ | 2 | ▢ | 1 | 0 | - | ||
| 3 | return y | 3 | ▢ | 2 | ▢ | 1 | 0 | - | d(1)=0 | |
| 2 | sortie de 'd(1)' | 3 | ▢ | 2 | ▢ | - | - | - | ||
| 2 | Affectation y=d(n-1) | 3 | ▢ | 2 | 0 | - | - | - | ||
| 2 | return y | 3 | ▢ | 2 | 0 | - | - | - | d(2)=0 | |
| 1 | sortie de 'd(2)' | 3 | ▢ | - | - | - | - | - | ||
| 1 | Affectation y=d(n-1) | 3 | 0 | - | - | - | - | - | ||
| 1 | return y | 3 | 0 | - | - | - | - | - | d(3)=0 | |
| 0 | sortie de 'd(3)' | - | - | - | - | - | - | - |
La dernière étape se fait en-dehors de la fonction :
print( "Valeur de d({}) : {}.".format(n, d(n)) ) affiche la valeur de d(3), c'est à dire 0.
On présente une petite variante du programme précédent.
Seules deux lignes sont interverties dans le programme par rapport au précédent.
Chercher à analyser ce que sera l'affichage avant de tester le programme.
def c(n) :
if n==0 :
return 0
else :
y=c(n-1)
print(n)
return y
n=3
print( "Valeur de c({}) : {}.".format(n, c(n)) )
Réponse de python :
1 2 3 Valeur de c(3) : 0.
On constate que les affichages intermédiaires (les affichages internes à la fonction) sont inversés par rapport au programme précédent.
Schématisons le déroulement pour tenter de mieux saisir le fonctionnement.
Tout d'abord, la 'descente' :
| Profondeur | Instructions | n1 | y1 | n2 | y2 | n3 | y3 | n4 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | Appel de la fonction d | 3 | - | - | - | - | - | - | ||
| 1 | (n==0) faux | 3 | - | - | - | - | - | - | ||
| 1 | y= | 3 | ▢ | - | - | - | - | - | ||
| 2 | c(n-1) | 3 | ▢ | 2 | - | - | - | - | ||
| 2 | (n==0) faux | 3 | ▢ | 2 | - | - | - | - | ||
| 2 | y= | 3 | ▢ | 2 | ▢ | - | - | - | ||
| 3 | c(n-1) | 3 | ▢ | 2 | ▢ | 1 | - | - | ||
| 3 | (n==0) faux | 3 | ▢ | 2 | ▢ | 1 | - | - | ||
| 3 | y= | 3 | ▢ | 2 | ▢ | 1 | ▢ | - | ||
| 4 | c(n-1) | 3 | ▢ | 2 | ▢ | 1 | ▢ | 0 | ||
| 4 | (n==0) vrai | 3 | ▢ | 2 | ▢ | 1 | ▢ | 0 | ||
| 4 | return 0 | 3 | ▢ | 2 | ▢ | 1 | ▢ | 0 | c(0)=0 |
Ensuite, la 'remontée' :
| Profondeur | Instructions | n1 | y1 | n2 | y2 | n3 | y3 | n4 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|---|---|---|
| 3 | sortie de 'c(0)' | 3 | ▢ | 2 | ▢ | 1 | ▢ | - | ||
| 3 | affectation y=c(n-1) | 3 | ▢ | 2 | ▢ | 1 | 0 | - | ||
| 3 | print(n) | 3 | ▢ | 2 | ▢ | 1 | 0 | - | 1 | |
| 3 | return y | 3 | ▢ | 2 | ▢ | 1 | 0 | - | c(1)=0 |
Et on continue :
| Profondeur | Instructions | n1 | y1 | n2 | y2 | n3 | y3 | n4 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|---|---|---|
| 2 | sortie de 'c(1)' | 3 | ▢ | 2 | ▢ | - | - | - | ||
| 2 | Affectation y=c(n-1) | 3 | ▢ | 2 | 0 | - | - | - | ||
| 2 | print(n) | 3 | ▢ | 2 | 0 | - | - | - | 2 | |
| 2 | return y | 3 | ▢ | 2 | 0 | - | - | - | c(2)=0 |
On poursuit :
| Profondeur | Instructions | n1 | y1 | n2 | y2 | n3 | y3 | n4 | Affichage | Valeur retournée |
|---|---|---|---|---|---|---|---|---|---|---|
| 1 | sortie de 'c(2)' | 3 | ▢ | - | - | - | - | - | ||
| 1 | Affectation y=c(n-1) | 3 | 0 | - | - | - | - | - | ||
| 1 | print(n) | 3 | 0 | - | - | - | - | - | 3 | |
| 1 | return y | 3 | 0 | - | - | - | - | - | c(3)=0 | |
| 0 | sortie de 'c(3)' | - | - | - | - | - | - | - |
La dernière étape se fait en-dehors de la fonction :
print( "Valeur de c({}) : {}.".format(n, c(n)) ) affiche la valeur de c(3), c'est à dire 0.
Aucun affichage n'a lieu durant la "descente", les affichages sont repoussés après les appels
à la fonction alors que l'on est passé à un niveau plus profond d'appel. Ceci explique l'inversion des affichages.
Attachez vous à comprendre ces deux programmes,
vous aurez saisi l'essentiel de ce que vous devez savoir sur les fonctions récursives.