Livre_silo 30 août 2013 16:32 Page 136
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
136
Informatique pour tous
Si on a utilisé un schéma de récurrence forte pour définir une fonction récursive, alors
il faudra bien entendu en démontrer la correction par récurrence forte également. Avec
l’exemple de la fonction puissance_rapide page 134, on cherche à montrer par récurrence
forte sur n ⩾ 0 la propriété suivante :
H n : puissance_rapide(x, n) termine et renvoie la valeur x
n
La propriété H 0 est vérifiée car puissance_rapide(x, 0) se réduit à return 1 (en admettant
que l’on a posé 0
0 = 1 arbitrairement). Soit maintenant n > 0 ; on suppose H i pour
tout 0 ⩽ i < n et on veut montrer H n . Le calcul de puissance_rapide(x, n) commence
par un appel récursif r = puissance_rapide(x, n // 2). On pose k = ⌊
n
2 ⌋. Comme n > 0,
on a k < n. On peut donc appliquer l’hypothèse de récurrence H k , qui affirme que l’appel puissance_rapide(x, n // 2) termine et renvoie la valeur x
k . On distingue alors deux
cas, selon la parité de n. Si n est pair, c’est-à-dire n = 2k, alors le programme effectue
return r * r. Donc il termine et renvoie x
k
× x
k = x
2k = x
n , ce qui démontre H n . On
procède de même lorsque n est impair.
Exercice 5.10 ** Démontrer la terminaison et la correction de la fonction puissance page 133.
Exercice 5.11 Montrer la correction de la fonction briques définie plus haut (page 134).
Exercice 5.12 ** Que se passe-t-il avec la fonction puissance_rapide si on écrit n / 2 au lieu de n // 2
(en Python 3) ou encore n / 2. ?
ATTENTION Limitation de la récursivité en Python
Le langage Python limite, arbitrairement, le nombre d’appels imbriqués à 1 000. Une fonction qui fait plus de 1 000 appels récursifs provoque l’erreur suivante :
RuntimeError: maximum recursion depth exceeded
Même si cette limite semble basse, elle n’exclut pas pour autant l’utilisation de fonctions
récursives en Python. En effet, il existe de nombreuses situations où l’on sait que le nombre
d’appels sera bien inférieur à 1 000. C’est le cas en particulier pour des fonctions qui font un
nombre d’appels logarithmique en la taille des données. Voir par exemple l’exercice 5.15.
POUR ALLER PLUS LOIN Démontrer la terminaison d’une fonction récursive
De même qu’on peut justifier la terminaison d’une boucle en exhibant un entier naturel
qui décroît strictement à chaque itération (voir page 98), on peut démontrer la terminaison d’une boucle récursive en exhibant en entier naturel qui décroît strictement à chaque
appel récursif. Le plus souvent, il s’agira directement de l’un des arguments de la fonction
récursive, comme dans le cas des fonctions définies plus haut dans cette section.
¯
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
136
Informatique pour tous
Si on a utilisé un schéma de récurrence forte pour définir une fonction récursive, alors
il faudra bien entendu en démontrer la correction par récurrence forte également. Avec
l’exemple de la fonction puissance_rapide page 134, on cherche à montrer par récurrence
forte sur n ⩾ 0 la propriété suivante :
H n : puissance_rapide(x, n) termine et renvoie la valeur x
n
La propriété H 0 est vérifiée car puissance_rapide(x, 0) se réduit à return 1 (en admettant
que l’on a posé 0
0 = 1 arbitrairement). Soit maintenant n > 0 ; on suppose H i pour
tout 0 ⩽ i < n et on veut montrer H n . Le calcul de puissance_rapide(x, n) commence
par un appel récursif r = puissance_rapide(x, n // 2). On pose k = ⌊
n
2 ⌋. Comme n > 0,
on a k < n. On peut donc appliquer l’hypothèse de récurrence H k , qui affirme que l’appel puissance_rapide(x, n // 2) termine et renvoie la valeur x
k . On distingue alors deux
cas, selon la parité de n. Si n est pair, c’est-à-dire n = 2k, alors le programme effectue
return r * r. Donc il termine et renvoie x
k
× x
k = x
2k = x
n , ce qui démontre H n . On
procède de même lorsque n est impair.
Exercice 5.10 ** Démontrer la terminaison et la correction de la fonction puissance page 133.
Exercice 5.11 Montrer la correction de la fonction briques définie plus haut (page 134).
Exercice 5.12 ** Que se passe-t-il avec la fonction puissance_rapide si on écrit n / 2 au lieu de n // 2
(en Python 3) ou encore n / 2. ?
ATTENTION Limitation de la récursivité en Python
Le langage Python limite, arbitrairement, le nombre d’appels imbriqués à 1 000. Une fonction qui fait plus de 1 000 appels récursifs provoque l’erreur suivante :
RuntimeError: maximum recursion depth exceeded
Même si cette limite semble basse, elle n’exclut pas pour autant l’utilisation de fonctions
récursives en Python. En effet, il existe de nombreuses situations où l’on sait que le nombre
d’appels sera bien inférieur à 1 000. C’est le cas en particulier pour des fonctions qui font un
nombre d’appels logarithmique en la taille des données. Voir par exemple l’exercice 5.15.
POUR ALLER PLUS LOIN Démontrer la terminaison d’une fonction récursive
De même qu’on peut justifier la terminaison d’une boucle en exhibant un entier naturel
qui décroît strictement à chaque itération (voir page 98), on peut démontrer la terminaison d’une boucle récursive en exhibant en entier naturel qui décroît strictement à chaque
appel récursif. Le plus souvent, il s’agira directement de l’un des arguments de la fonction
récursive, comme dans le cas des fonctions définies plus haut dans cette section.
¯