Livre_silo 30 août 2013 16:32 Page 130
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
130
Informatique pour tous
Cette méthode fonctionne également avec une liste de chaînes pour argument :
In [16]: ' '.join(['Ceci', 'est', 'une', 'phrase'])
Out[16]: 'Ceci est une phrase'
On réalise l’opération duale, c’est-à-dire découper une chaîne selon un séparateur donné,
à l’aide la méthode split :
In [17]: 'Ceci est une phrase'.split('')
Out[17]: ['Ceci', 'est', 'une', 'phrase']
D’autres méthodes seront présentées dans la suite de cet ouvrage, notamment pour manipuler les piles et effectuer des entrées/sorties dans des fichiers.
5.3 La récursivité
Avertissement : les contenus abordés dans cette section sont au programme de seconde année uniquement. En particulier, certains exercices nécessitent d’avoir traité la complexité (section 6.1).
On considère la suite (u n ) suivante, qui calcule une approximation de
√
3 :
u 0 = 2
u n =
1
2
(
u n−1 +
3
u n−1
)
On peut calculer cette suite à l’aide d’une fonction u, qui prend un argument n, et telle que
u(n) renvoie la valeur de u n . En Python, on peut écrire la fonction u en suivant directement
la définition précédente :
def u(n):
if n == 0:
return 2.
else:
return 0.5 * (u(n-1) + 3. / u(n-1))
On remarque que dans la dernière ligne, il y a deux appels à la fonction pour calculer
u n−1 . En effet, rien n’interdit d’appeler la fonction u à l’intérieur de son propre corps.
On nomme alors cela une fonction récursive. Pour plus d’efficacité, on peut « factoriser »
les deux appels u(n-1) en stockant le résultat dans une variable locale, ce qui supprime un
appel potentiellement coûteux à u :
...
else:
x = u(n-1)
return 0.5 * (x + 3. / x)
Ainsi, pour calculer une valeur approchée de
√
3, il suffit d’écrire le programme suivant :
print(u(2))
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
130
Informatique pour tous
Cette méthode fonctionne également avec une liste de chaînes pour argument :
In [16]: ' '.join(['Ceci', 'est', 'une', 'phrase'])
Out[16]: 'Ceci est une phrase'
On réalise l’opération duale, c’est-à-dire découper une chaîne selon un séparateur donné,
à l’aide la méthode split :
In [17]: 'Ceci est une phrase'.split('')
Out[17]: ['Ceci', 'est', 'une', 'phrase']
D’autres méthodes seront présentées dans la suite de cet ouvrage, notamment pour manipuler les piles et effectuer des entrées/sorties dans des fichiers.
5.3 La récursivité
Avertissement : les contenus abordés dans cette section sont au programme de seconde année uniquement. En particulier, certains exercices nécessitent d’avoir traité la complexité (section 6.1).
On considère la suite (u n ) suivante, qui calcule une approximation de
√
3 :
u 0 = 2
u n =
1
2
(
u n−1 +
3
u n−1
)
On peut calculer cette suite à l’aide d’une fonction u, qui prend un argument n, et telle que
u(n) renvoie la valeur de u n . En Python, on peut écrire la fonction u en suivant directement
la définition précédente :
def u(n):
if n == 0:
return 2.
else:
return 0.5 * (u(n-1) + 3. / u(n-1))
On remarque que dans la dernière ligne, il y a deux appels à la fonction pour calculer
u n−1 . En effet, rien n’interdit d’appeler la fonction u à l’intérieur de son propre corps.
On nomme alors cela une fonction récursive. Pour plus d’efficacité, on peut « factoriser »
les deux appels u(n-1) en stockant le résultat dans une variable locale, ce qui supprime un
appel potentiellement coûteux à u :
...
else:
x = u(n-1)
return 0.5 * (x + 3. / x)
Ainsi, pour calculer une valeur approchée de
√
3, il suffit d’écrire le programme suivant :
print(u(2))