Livre_silo 30 août 2013 16:32 Page 134
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
134
Informatique pour tous
L’ écriture de fonctions récursives n’est pas limitée au schéma de récurrence simple. On
peut également utiliser un schéma de récurrence forte, c’est-à-dire effectuer des appels
récursifs sur des valeurs strictement inférieures à n-1. Reprenant l’exemple du calcul de x
n ,
on propose un meilleur algorithme qui exploite les deux identités suivantes :
x
2k
= (x
k )
2
x
2k+1
= x(x
k )
2
Elles permettent de ramener le calcul de x
n à celui de x
⌊
n
2 ⌋ . Le cas de base reste le même,
à savoir x
0 = 1. Dans le cas récursif, on commence par calculer x
⌊
n
2 ⌋ dans une variable r,
puis on teste la parité de n pour choisir entre les deux identités ci-avant. Finalement, on
obtient le code suivant :
def puissance_rapide(x, n):
if n == 0:
return 1
else:
r = puissance_rapide(x, n // 2)
if n % 2 == 0:
return r * r
else:
return x * r * r
Ainsi, le calcul de puissance_rapide(3, 5) se ramène directement au calcul de
puissance_rapide(3, 2) et évite les appels à puissance_rapide(3, 3) et puissance_rapide(3, 4).
Exercice 5.9 * Écrire une variante (toujours récursive) de la fonction puissance_rapide qui exploite plutôt
les identités suivantes :
{
x 2k = (x 2 ) k
x 2k+1 = x(x 2 ) k
Y a-t-il une différence dans le nombre de multiplications effectuées ?
Pour continuer l’analogie avec le principe de récurrence forte en mathématiques, il est
parfois nécessaire d’effectuer plusieurs appels récursifs pour calculer f(n). On considère le
problème consistant à calculer le nombre de façons de construire une rangée de longueur n
avec des briques de longueur 2 et 3. Voici par exemple deux rangées de longueur n = 14.
On peut en dénombrer 21 au total. Les cas de base correspondent à n = 1 (pas de solution)
et 2 ⩽ n ⩽ 3 (une solution unique). Le calcul récursif consiste à se ramener au cas n − 2
(ajout d’une brique de longueur 2) et au cas n − 3 (ajout d’une brique de longueur 3).
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
134
Informatique pour tous
L’ écriture de fonctions récursives n’est pas limitée au schéma de récurrence simple. On
peut également utiliser un schéma de récurrence forte, c’est-à-dire effectuer des appels
récursifs sur des valeurs strictement inférieures à n-1. Reprenant l’exemple du calcul de x
n ,
on propose un meilleur algorithme qui exploite les deux identités suivantes :
x
2k
= (x
k )
2
x
2k+1
= x(x
k )
2
Elles permettent de ramener le calcul de x
n à celui de x
⌊
n
2 ⌋ . Le cas de base reste le même,
à savoir x
0 = 1. Dans le cas récursif, on commence par calculer x
⌊
n
2 ⌋ dans une variable r,
puis on teste la parité de n pour choisir entre les deux identités ci-avant. Finalement, on
obtient le code suivant :
def puissance_rapide(x, n):
if n == 0:
return 1
else:
r = puissance_rapide(x, n // 2)
if n % 2 == 0:
return r * r
else:
return x * r * r
Ainsi, le calcul de puissance_rapide(3, 5) se ramène directement au calcul de
puissance_rapide(3, 2) et évite les appels à puissance_rapide(3, 3) et puissance_rapide(3, 4).
Exercice 5.9 * Écrire une variante (toujours récursive) de la fonction puissance_rapide qui exploite plutôt
les identités suivantes :
{
x 2k = (x 2 ) k
x 2k+1 = x(x 2 ) k
Y a-t-il une différence dans le nombre de multiplications effectuées ?
Pour continuer l’analogie avec le principe de récurrence forte en mathématiques, il est
parfois nécessaire d’effectuer plusieurs appels récursifs pour calculer f(n). On considère le
problème consistant à calculer le nombre de façons de construire une rangée de longueur n
avec des briques de longueur 2 et 3. Voici par exemple deux rangées de longueur n = 14.
On peut en dénombrer 21 au total. Les cas de base correspondent à n = 1 (pas de solution)
et 2 ⩽ n ⩽ 3 (une solution unique). Le calcul récursif consiste à se ramener au cas n − 2
(ajout d’une brique de longueur 2) et au cas n − 3 (ajout d’une brique de longueur 3).