TP1 - Premiers pas avec la récursivité
À la fin de ce TP, vous devez être capable de :
- identifier le cas d'arrêt et le cas général d'une fonction récursive ;
- prévoir les appels successifs d'une fonction récursive ;
- repérer une récursion incorrecte ;
- compléter puis écrire une fonction récursive simple.
Suivre les appels d'une fonction
Observez la fonction suivante sans l'exécuter :
def compte_a_rebours(n):
print(n)
if n > 0:
compte_a_rebours(n - 1)
On considère l'appel :
compte_a_rebours(4)
Exercices
- 1
Quelle valeur est affichée lors du premier appel ?
- 2
Quel est l'appel récursif effectué ensuite ?
- 3
Compléter la suite des appels :
compte_a_rebours(4)
→ compte_a_rebours(...)
→ compte_a_rebours(...)
→ compte_a_rebours(...)
→ compte_a_rebours(...) - 4
Quelles valeurs sont affichées, dans l'ordre ?
- 5
Combien de fois la fonction est-elle appelée au total ?
- 6
Identifier le cas d'arrêt de la fonction.
- 7
Identifier son cas général.
- 8
Tester seulement maintenant votre réponse avec Python.
Prévoir le résultat avant d'exécuter
On considère les deux fonctions suivantes :
def fonction_a(n):
if n == 0:
print("Fin")
else:
print(n)
fonction_a(n - 1)
def fonction_b(n):
if n == 0:
print("Fin")
else:
fonction_b(n - 1)
print(n)
Exercices
- 1
Sans exécuter le programme, prévoir l'affichage produit par :
fonction_a(3) - 2
Prévoir maintenant l'affichage produit par :
fonction_b(3) - 3
Les deux fonctions possèdent-elles le même cas d'arrêt ?
- 4
Les appels récursifs sont-ils différents ?
- 5
Expliquer pourquoi les nombres ne sont pas affichés dans le même ordre.
- 6
Vérifier vos réponses avec Python.
Repérer les fonctions incorrectes
Pour chacune des fonctions suivantes, ne l'exécutez pas immédiatement.
def fonction_a(n):
if n == 0:
return 0
return fonction_a(n - 1)
def fonction_b(n):
if n == 0:
return 0
return fonction_b(n + 1)
def fonction_c(n):
return fonction_c(n - 1)
def fonction_d(n):
if n <= 0:
return 0
return fonction_d(n - 2)
Exercices
Pour chaque fonction appelée avec n = 5 :
- 1
Identifier, s'il existe, le cas d'arrêt.
- 2
Indiquer comment évolue
nlors des appels successifs. - 3
Dire si la fonction atteindra son cas d'arrêt.
- 4
En déduire si l'appel se terminera correctement.
- 5
Corriger les fonctions qui ne se terminent pas correctement.
Compléter une première fonction récursive
On souhaite écrire une fonction afficher_pairs(n) qui affiche les nombres pairs de n jusqu'à 0.
On suppose que n est un entier positif pair.
Par exemple :
afficher_pairs(6)
doit afficher :
6
4
2
0
Exercices
- 1
Quelle valeur de
npeut servir de cas d'arrêt ? - 2
De combien faut-il diminuer
nà chaque appel ? - 3
Compléter la fonction :
def afficher_pairs(n):
print(n)
if ................:
afficher_pairs(................) - 4
Tester votre fonction avec
afficher_pairs(10). - 5
Modifier ensuite la fonction pour qu'elle affiche les nombres pairs dans l'ordre croissant, de
0jusqu'àn.
Travailler avec une valeur de retour
On considère la fonction suivante :
def somme(n):
if n == 0:
return 0
else:
return n + somme(n - 1)
Exercices
- 1
Donner le résultat de
somme(4)sans exécuter le programme. - 2
Compléter la phase de descente :
somme(4)
= 4 + somme(...)
= 4 + 3 + somme(...)
= 4 + 3 + 2 + somme(...)
= 4 + 3 + 2 + 1 + somme(...) - 3
Quelle valeur est renvoyée par le cas d'arrêt ?
- 4
Compléter ensuite la remontée :
somme(0) = ...
somme(1) = ...
somme(2) = ...
somme(3) = ...
somme(4) = ... - 5
Vérifier avec Python.
Compléter une fonction qui renvoie une valeur
On souhaite calculer avec une fonction récursive puissance2(n).
On utilisera les relations suivantes :
2⁰ = 1
2ⁿ = 2 × 2ⁿ⁻¹
Exercices
- 1
Identifier le cas d'arrêt.
- 2
Quelle valeur doit être renvoyée dans ce cas ?
- 3
Dans le cas général, avec quelle valeur doit-on rappeler
puissance2? - 4
Compléter :
def puissance2(n):
if ................:
return ................
else:
return 2 * ................ - 5
Vérifier votre fonction avec :
assert puissance2(0) == 1
assert puissance2(1) == 2
assert puissance2(4) == 16
assert puissance2(8) == 256
Écrire une fonction récursive
On souhaite créer une fonction somme_pairs(n) qui renvoie la somme des nombres pairs de n jusqu'à 0.
On suppose que n est un entier positif pair.
Par exemple :
somme_pairs(6) = 6 + 4 + 2 + 0 = 12
Exercices
- 1
Déterminer le cas d'arrêt.
- 2
Déterminer la valeur à renvoyer dans ce cas.
- 3
Déterminer comment obtenir un problème plus petit à partir de
n. - 4
Écrire entièrement la fonction
somme_pairs(n). - 5
Vérifier votre fonction avec :
assert somme_pairs(0) == 0
assert somme_pairs(2) == 2
assert somme_pairs(6) == 12
assert somme_pairs(10) == 30
Modifier un problème connu
On souhaite maintenant écrire une fonction produit(n) qui calcule :
n × (n - 1) × (n - 2) × ... × 1
Par exemple :
produit(4) = 4 × 3 × 2 × 1 = 24
Exercices
- 1
Proposer un cas d'arrêt et la valeur à renvoyer dans ce cas.
- 2
Exprimer
produit(4)à l'aide deproduit(3). - 3
En déduire l'expression du cas général pour
produit(n). - 4
Écrire entièrement la fonction récursive
produit(n). - 5
Vérifier avec :
assert produit(1) == 1
assert produit(3) == 6
assert produit(5) == 120
Aller plus loin
Écrire une fonction récursive compter_chiffres(n) qui renvoie le nombre de chiffres d'un entier strictement positif n.
Par exemple :
compter_chiffres(5382)
doit renvoyer 4.
On rappelle que la division entière par 10 permet de supprimer le dernier chiffre d'un entier :
5382 // 10 = 538
538 // 10 = 53
53 // 10 = 5
Exercices
- 1
À partir de quelle situation peut-on savoir immédiatement qu'il ne reste qu'un seul chiffre ?
- 2
Comment transformer
npour se rapprocher de cette situation ? - 3
Écrire la fonction
compter_chiffres(n). - 4
Vérifier avec :
assert compter_chiffres(7) == 1
assert compter_chiffres(42) == 2
assert compter_chiffres(5382) == 4
assert compter_chiffres(100000) == 6