Livre_silo 30 août 2013 16:32 Page 139
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
139
5 – Fonctions
Une autre manière d’évaluer le coût d’une fonction récursive est de calculer le nombre
d’appels, puis d’évaluer le coût de chaque appel. Si on note A(n) le nombre d’appels récursifs dans les deux exemples précédents, on a :
A(0) = 0
A(n) = A(n − 1) + 1
dans le premier cas, et :
A(0) = 0
A(n) = A(n − 1) + A(n − 1) + 1
dans le second cas. Le terme général est donc A(n) = n dans le premier cas et
A(n) = 2
n
− 1 dans le second. Puisqu’on n’a ici aucune opération arithmétique dans
le cas de base n = 0 et exactement trois opérations arithmétiques dans le cas récursif, on
retrouve immédiatement la valeur de C(n) calculée précédemment. D’une manière générale, la valeur de C(n) ne se déduit pas toujours aussi facilement de la valeur de A(n).
En effet, il peut y avoir des opérations dans le cas de base et/ou un nombre d’opérations
arithmétiques variant selon la valeur de n dans le cas récursif.
Comme nous l’avons expliqué page 131, chaque appel récursif alloue de la mémoire pour
les paramètres effectifs et les variables locales de cet appel. L’occupation mémoire d’un
calcul récursif admet donc pour majorant le produit du nombre d’appels récursifs par la
quantité de mémoire allouée par chaque appel. Dans les deux exemples précédents, on a
calculé explicitement le nombre d’appels A(n). L’occupation mémoire est donc 2n dans le
premier cas (il y a deux cases mémoire, une pour n et une autre pour x) et 2
n
− 1 dans le
second cas (il y a une case mémoire, pour n). Cependant, dans le second cas, les 2
n
−1 cases
mémoire ne seront pas utilisées simultanément. En effet, celles allouées pour le premier
appel à u(n-1) peuvent être réutilisées pour le second (et en pratique elles le sont). Pour une
analyse plus fine de l’occupation mémoire, il convient donc de calculer le nombre d’appels
imbriqués.
Exercice 5.14 On considère la première version de la fonction puissance, définie p. 133.
1 Combien effectue-t-elle exactement d’appels récursifs pour calculer x n ?
2 Quel est son coût en mémoire ?
Exercice 5.15 * On considère la fonction puissance_rapide définie p. 134.
1 Montrer qu’elle calcule x n en effectuant un nombre total d’appels récursifs proportionnel à log n.
2 A-t-on la même complexité quand on n’utilise pas de variable locale r, mais que l’on écrit directement :
puissance_rapide(x, n // 2) * puissance_rapide(x, n // 2) à la place de r * r ?
5.4 Exercices
Exercice 5.16 Écrire en Python une fonction qui prend comme argument un entier n et renvoie l’entier 2 n .
Exercice 5.17 * Écrire en Python une fonction qui prend comme argument un entier n et renvoie un
booléen qui indique si cet entier est premier ou non.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
139
5 – Fonctions
Une autre manière d’évaluer le coût d’une fonction récursive est de calculer le nombre
d’appels, puis d’évaluer le coût de chaque appel. Si on note A(n) le nombre d’appels récursifs dans les deux exemples précédents, on a :
A(0) = 0
A(n) = A(n − 1) + 1
dans le premier cas, et :
A(0) = 0
A(n) = A(n − 1) + A(n − 1) + 1
dans le second cas. Le terme général est donc A(n) = n dans le premier cas et
A(n) = 2
n
− 1 dans le second. Puisqu’on n’a ici aucune opération arithmétique dans
le cas de base n = 0 et exactement trois opérations arithmétiques dans le cas récursif, on
retrouve immédiatement la valeur de C(n) calculée précédemment. D’une manière générale, la valeur de C(n) ne se déduit pas toujours aussi facilement de la valeur de A(n).
En effet, il peut y avoir des opérations dans le cas de base et/ou un nombre d’opérations
arithmétiques variant selon la valeur de n dans le cas récursif.
Comme nous l’avons expliqué page 131, chaque appel récursif alloue de la mémoire pour
les paramètres effectifs et les variables locales de cet appel. L’occupation mémoire d’un
calcul récursif admet donc pour majorant le produit du nombre d’appels récursifs par la
quantité de mémoire allouée par chaque appel. Dans les deux exemples précédents, on a
calculé explicitement le nombre d’appels A(n). L’occupation mémoire est donc 2n dans le
premier cas (il y a deux cases mémoire, une pour n et une autre pour x) et 2
n
− 1 dans le
second cas (il y a une case mémoire, pour n). Cependant, dans le second cas, les 2
n
−1 cases
mémoire ne seront pas utilisées simultanément. En effet, celles allouées pour le premier
appel à u(n-1) peuvent être réutilisées pour le second (et en pratique elles le sont). Pour une
analyse plus fine de l’occupation mémoire, il convient donc de calculer le nombre d’appels
imbriqués.
Exercice 5.14 On considère la première version de la fonction puissance, définie p. 133.
1 Combien effectue-t-elle exactement d’appels récursifs pour calculer x n ?
2 Quel est son coût en mémoire ?
Exercice 5.15 * On considère la fonction puissance_rapide définie p. 134.
1 Montrer qu’elle calcule x n en effectuant un nombre total d’appels récursifs proportionnel à log n.
2 A-t-on la même complexité quand on n’utilise pas de variable locale r, mais que l’on écrit directement :
puissance_rapide(x, n // 2) * puissance_rapide(x, n // 2) à la place de r * r ?
5.4 Exercices
Exercice 5.16 Écrire en Python une fonction qui prend comme argument un entier n et renvoie l’entier 2 n .
Exercice 5.17 * Écrire en Python une fonction qui prend comme argument un entier n et renvoie un
booléen qui indique si cet entier est premier ou non.