Livre_silo 30 août 2013 16:32 Page 133
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
133
5 – Fonctions
De la même façon, on peut définir une fonction f prenant en argument un entier naturel n
en se ramenant au calcul de f(0) d’une part et de f(n) en fonction de f(n-1) d’autre part.
La fonction f prend alors la forme suivante :
def f(n):
if n == 0:
return ...
else:
return ... f(n-1) ...
L’exemple le plus classique est sûrement celui de la fonction factorielle, dont la définition
est donnée page 104 :
def factorielle(n):
if n == 0:
return 1
else:
return n * factorielle(n-1)
Il est important de noter qu’une telle fonction ne terminera pas sur un argument n négatif.
En effet, factorielle(-1) appellerait factorielle(-2), qui appellerait factorielle(-3), etc. Il
s’agit donc d’une fonction partielle, à laquelle on peut appliquer toute solution discutée
dans la section 5.2.3. En particulier, on peut s’assurer que n est bien un entier naturel en
écrivant :
def factorielle(n):
assert n >= 0
...
Le schéma de récurrence simple peut être appliqué à des fonctions ayant d’autres arguments que n. Ainsi, la fonction puissance qui calcule x à la puissance n peut facilement être
définie par récurrence simple sur n, de la manière suivante :
def puissance(x, n):
if n == 0:
return 1
else:
return x * puissance(x, n-1)
Comme en mathématiques, le schéma de récurrence simple peut être adapté à des définitions impliquant plusieurs cas de base. Ainsi, on évite une multiplication inutile quand n
vaut 1 dans la fonction puissance en la réécrivant de la façon suivante :
def puissance(x, n):
if n == 0:
return 1
elif n == 1:
return x
else:
return x * puissance(x, n-1)