Livre_silo 30 août 2013 16:32 Page 132
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
132
Informatique pour tous
Seule une nouvelle case pour n est allouée en mémoire (puisque la branche else n’est pas
exécutée). L’appel u(0) se termine alors par return 2., ce qui a pour effet, non seulement
de supprimer de la mémoire les variables locales allouées pour cet appel, mais également
d’affecter la valeur 2. à la variable x de l’appel précédent. On se trouve alors dans l’état
mémoire suivant :
u(1)
. .
1 .
n
. .
2. .
x
u(2)
. .
2 .
n
. .
? .
x
De la même manière, l’appel u(1) se termine par return 0.5 * (2. + 3. / 2.) et on revient à
l’état mémoire du premier appel :
u(2)
. .
2 .
n
. .
1.75 .
x
Enfin, l’appel u(2) se termine et la fonction renvoie la valeur 1.7321428571428572 comme
approximation de
√
3.
POUR ALLER PLUS LOIN Dérécursivation
Il était également possible d’écrire une version non récursive de la fonction u en utilisant
une boucle, par exemple sous la forme suivante :
def u(n):
r = 2.
for i in range(n):
r = 0.5 * (r + 3. / r)
return r
Les mêmes calculs sont effectués, dans le même ordre. Cependant, le rapprochement
avec la définition de la suite (un) est moins évident. En particulier, dans l’instruction
r = 0.5 * (r + 3. / r), il faut comprendre que l’occurrence de r dans le membre droit désigne u i et que celle de r dans le membre gauche désigne u i+1 . Puisqu’on termine avec
i = n − 1, on a bien calculé un.
5.3.1 Concevoir une fonction récursive
La conception d’une fonction récursive n’est pas éloignée du principe de démonstration
par récurrence. Par exemple, le principe de récurrence simple permet de démontrer une
propriété P n pour tout n ∈ N en démontrant d’une part le cas de base P 0 et d’autre part
que P n−1 implique P n pour tout n > 0.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
132
Informatique pour tous
Seule une nouvelle case pour n est allouée en mémoire (puisque la branche else n’est pas
exécutée). L’appel u(0) se termine alors par return 2., ce qui a pour effet, non seulement
de supprimer de la mémoire les variables locales allouées pour cet appel, mais également
d’affecter la valeur 2. à la variable x de l’appel précédent. On se trouve alors dans l’état
mémoire suivant :
u(1)
. .
1 .
n
. .
2. .
x
u(2)
. .
2 .
n
. .
? .
x
De la même manière, l’appel u(1) se termine par return 0.5 * (2. + 3. / 2.) et on revient à
l’état mémoire du premier appel :
u(2)
. .
2 .
n
. .
1.75 .
x
Enfin, l’appel u(2) se termine et la fonction renvoie la valeur 1.7321428571428572 comme
approximation de
√
3.
POUR ALLER PLUS LOIN Dérécursivation
Il était également possible d’écrire une version non récursive de la fonction u en utilisant
une boucle, par exemple sous la forme suivante :
def u(n):
r = 2.
for i in range(n):
r = 0.5 * (r + 3. / r)
return r
Les mêmes calculs sont effectués, dans le même ordre. Cependant, le rapprochement
avec la définition de la suite (un) est moins évident. En particulier, dans l’instruction
r = 0.5 * (r + 3. / r), il faut comprendre que l’occurrence de r dans le membre droit désigne u i et que celle de r dans le membre gauche désigne u i+1 . Puisqu’on termine avec
i = n − 1, on a bien calculé un.
5.3.1 Concevoir une fonction récursive
La conception d’une fonction récursive n’est pas éloignée du principe de démonstration
par récurrence. Par exemple, le principe de récurrence simple permet de démontrer une
propriété P n pour tout n ∈ N en démontrant d’une part le cas de base P 0 et d’autre part
que P n−1 implique P n pour tout n > 0.