Devoir n°1
Récursivité
30 minutes
On s’intéresse à la fonction récursive puissance définie en Python de la manière suivante :
def puissance(x, n):
if n == 0: return 1
else: return x * puissance(x, n - 1)
1. On exécute l’instruction puissance(2, 3).
Donner la valeur renvoyée et représenter l’exécution de cet appel à l’aide d’un arbre d’appels récursifs ou en décrivant l’évolution de la pile d’exécution (empilements successifs et calculs lors du dépilement).
2. Identifier dans le code de la fonction puissance la condition d’arrêt et préciser le cas de base ainsi que la valeur renvoyée dans ce cas.
3. Que se passe-t-il si on exécute l’instruction puissance(2, -1) ? Expliquer pourquoi la fonction n’atteint pas sa terminaison et préciser le nom de l’erreur levée par l’interpréteur Python.
4. On souhaite programmer une fonction récursive somme_premiers_entiers(n) qui prend en paramètre un entier positif ou nul $*n*$ et renvoie la somme des entiers de 0 jusqu’à $*n*$, c’est-à-dire la valeur de 0 + 1 + 2 + … + $*n*$.
Exemples :
somme_premiers_entiers(4)renvoie10car $*0 + 1 + 2 + 3 + 4 = 10*$ ;somme_premiers_entiers(0)renvoie0.
Écrire le code complet de la fonction récursive somme_premiers_entiers(n) en Python (sans utiliser de boucle for ou while, ni la fonction native sum).
Correction et barème
1. Valeur renvoyée : 8 (23 = 8).
Déroulement de l’exécution (arbre d’appels ou pile d’exécution) :
puissance(2, 3)appellepuissance(2, 2)et attend le résultat pour calculer 2×…puissance(2, 2)appellepuissance(2, 1)et attend le résultat pour calculer 2×…puissance(2, 1)appellepuissance(2, 0)et attend le résultat pour calculer 2×…puissance(2, 0)atteint le cas de base ($*n*$ == 0) et renvoie1.- Dépilement / calculs successifs :
puissance(2, 1)calcule $*2 \times 1 = 2*$ et renvoie 2puissance(2, 2)calcule $*2 \times 2 = 4*$ et renvoie 4puissance(2, 3)calcule $*2 \times 4 = 8*$ et renvoie 8
C si appels successifs mais renvois faux.
2. Cas de base et condition d'arrêt :
- Condition d’arrêt :
n == 0 - Cas de base : quand $*n*$ vaut 0, la fonction s’arrête d'effectuer des appels récursifs et renvoie la valeur
1.
-25 % si l’erreur levée par Python n’est pas mentionnée (même si le nom n’est pas explicité) ;
-25 % si pas d’explication claire sur pourquoi le cas de base n’est jamais atteint.
3. Appel avec puissance(2, -1) :
La variable $*n*$ vaut initialement -1. À chaque appel récursif, $*n*$ décroît de 1 (-2, puis -3, etc.). La condition d’arrêt $*n == 0*$ ne sera donc jamais atteinte.
Il se produit une récursion infinie (dépassement de la pile d’appels récursifs). L’interpréteur Python interrompt l'exécution en levant une exception RecursionError (dépassement de la profondeur maximale de récursion).
75 % l'explication de la non-terminaison, 25 % pour RecursionError (ou mention explicite de dépassement de pile).
4. Fonction récursive somme_premiers_entiers(n) :
def somme_premiers_entiers(n):
if n == 0: return 0
else: return n + somme_premiers_entiers(n - 1)
50 % pt pour le cas de base (n == 0 renvoie 0 ou n == 1 renvoie 1), 50 % pt pour l'appel récursif correct.