Livre_silo 30 août 2013 16:32 Page 135
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
135
5 – Fonctions
def briques(n):
assert n >= 1
if n == 1:
return 0
elif n == 2 or n == 3:
return 1
else:
return briques(n-2) + briques(n-3)
L’exercice 5.24 propose un autre exemple.
Enfin, il est parfois possible que la définition d’une fonction f fasse appel à une fonction g,
et que la définition de g fasse appel elle-même à celle de f. On parle alors de fonctions
mutuellement récursives. Par exemple, on peut définir une fonction pair pour déterminer si
un entier n est pair par récurrence mutuelle avec une fonction impair qui, elle, détermine
si un entier n est impair. En Python, il suffit d’écrire ces deux fonctions, l’une à la suite de
l’autre :
def pair(n):
return (n == 0) or impair(n-1)
def impair(n):
return (n != 0) and pair(n-1)
5.3.2 Terminaison et correction d’une fonction récursive
Dans cette section, on va montrer comment raisonner à propos d’une fonction récursive,
pour démontrer d’une part sa terminaison et d’autre part sa correction, c’est-à-dire le fait
qu’ elle calcule bien ce qu’elle doit calculer. Sans surprise, on utilisera le principe de démonstration par récurrence pour démontrer la correction d’une fonction récursive.
On va prendre l’exemple de la fonction factorielle définie plus haut page 133. On veut
montrer par récurrence sur n ⩾ 0 la propriété suivante :
H n : factorielle(n) termine et renvoie la valeur n!
La propriété H 0 est vérifiée car factorielle(0) se réduit à return 1. Pour n > 0, on suppose
H n−1 et on cherche à montrer H n . Le calcul de factorielle(n) commence par un appel
récursif à factorielle(n-1). Par hypothèse de récurrence, cet appel termine et renvoie la
valeur (n − 1)!. Puis l’appel à factorielle(n) multiplie ce résultat par n et renvoie le produit.
Donc, cet appel termine et renvoie bien n × (n − 1)! = n!, ce qui démontre H n .
Il est important de noter que nous n’avons rien démontré quant aux appels à la fonction
factorielle sur des arguments négatifs. En particulier, ils peuvent ne pas terminer (ce qui
est le cas ici), renvoyer des valeurs farfelues, ou encore échouer (ce qui serait le cas avec
assert n >= 0 par exemple).
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
135
5 – Fonctions
def briques(n):
assert n >= 1
if n == 1:
return 0
elif n == 2 or n == 3:
return 1
else:
return briques(n-2) + briques(n-3)
L’exercice 5.24 propose un autre exemple.
Enfin, il est parfois possible que la définition d’une fonction f fasse appel à une fonction g,
et que la définition de g fasse appel elle-même à celle de f. On parle alors de fonctions
mutuellement récursives. Par exemple, on peut définir une fonction pair pour déterminer si
un entier n est pair par récurrence mutuelle avec une fonction impair qui, elle, détermine
si un entier n est impair. En Python, il suffit d’écrire ces deux fonctions, l’une à la suite de
l’autre :
def pair(n):
return (n == 0) or impair(n-1)
def impair(n):
return (n != 0) and pair(n-1)
5.3.2 Terminaison et correction d’une fonction récursive
Dans cette section, on va montrer comment raisonner à propos d’une fonction récursive,
pour démontrer d’une part sa terminaison et d’autre part sa correction, c’est-à-dire le fait
qu’ elle calcule bien ce qu’elle doit calculer. Sans surprise, on utilisera le principe de démonstration par récurrence pour démontrer la correction d’une fonction récursive.
On va prendre l’exemple de la fonction factorielle définie plus haut page 133. On veut
montrer par récurrence sur n ⩾ 0 la propriété suivante :
H n : factorielle(n) termine et renvoie la valeur n!
La propriété H 0 est vérifiée car factorielle(0) se réduit à return 1. Pour n > 0, on suppose
H n−1 et on cherche à montrer H n . Le calcul de factorielle(n) commence par un appel
récursif à factorielle(n-1). Par hypothèse de récurrence, cet appel termine et renvoie la
valeur (n − 1)!. Puis l’appel à factorielle(n) multiplie ce résultat par n et renvoie le produit.
Donc, cet appel termine et renvoie bien n × (n − 1)! = n!, ce qui démontre H n .
Il est important de noter que nous n’avons rien démontré quant aux appels à la fonction
factorielle sur des arguments négatifs. En particulier, ils peuvent ne pas terminer (ce qui
est le cas ici), renvoyer des valeurs farfelues, ou encore échouer (ce qui serait le cas avec
assert n >= 0 par exemple).