Analyse de fonctions récursives - Série 2
Dans cette section, nous continuons l'analyse de fonctions récursives pour comprendre leur comportement et déterminer ce qu'elles calculent. La récursivité est un concept fondamental qui permet d'exprimer élégamment de nombreux algorithmes.
Analyse de fonction récursive - Somme cumulée
Expliquez la fonctionnalité de la fonction suivante :
fonction fct1(x, y)
SI x == 0 ALORS
retourne y
SINON
retourne fct1(x-1, x+y)
FINSIdef fct1(x, y):
if x == 0:
return y
else:
return fct1(x-1, x + y)La fonction fct1(x, y) calcule et retourne la somme des entiers de 1 à x, plus y, c'est-à-dire :
fct1(x, y) = (1 + 2 + ... + x) + y = x(x+1)/2 + y
Explication détaillée
- Cas de base : Si
x == 0, la fonction retourney. - Appel récursif : Sinon, elle s'appelle elle-même avec
x-1etx + ycomme nouveaux paramètres.
fct1(5, 2)
→ fct1(4, 5+2 = 7)
→ fct1(3, 4+7 = 11)
→ fct1(2, 3+11 = 14)
→ fct1(1, 2+14 = 16)
→ fct1(0, 1+16 = 17)
→ retourne 17On obtient 17, qui est bien (5×6/2) + 2 = 15 + 2 = 17.
Analyse de fonction récursive - Logarithme entier
Expliquez la fonctionnalité de la fonction suivante :
fonction fct2(n)
SI n == 1 ALORS
retourne 0
SINON
retourne 1 + fct2(n/2)
FINSIdef fct2(n):
if n == 1:
return 0
else:
return 1 + fct2(n // 2)La fonction fct2(n) calcule et retourne le logarithme entier en base 2 de n, c'est-à-dire le plus grand entier k tel que 2k ≤ n.
Formellement : fct2(n) = ⌊log₂(n)⌋
Explication détaillée
- Cas de base : Si
n == 1, la fonction retourne 0 (car 2⁰ = 1). - Appel récursif : Sinon, elle retourne 1 plus le résultat de l'appel récursif avec
n//2.
- Pour n = 1 → 0
- Pour n = 2 → 1 + fct2(1) = 1 + 0 = 1
- Pour n = 3 → 1 + fct2(1) = 1 + 0 = 1
- Pour n = 4 → 1 + fct2(2) = 1 + 1 = 2
- Pour n = 5 → 1 + fct2(2) = 1 + 1 = 2
- Pour n = 8 → 1 + fct2(4) = 1 + 2 = 3
Analyse de fonction récursive - Conversion binaire
Expliquez la fonctionnalité de la fonction suivante :
fonction fct3(n)
SI n == 0 ALORS
retourne
FINSI
fct3(n/2)
Ecrire(n % 2)def fct3(n):
if n == 0:
return
fct3(n // 2)
print(n % 2, end="")La fonction fct3(n) affiche la représentation binaire de l'entier n.
Elle utilise le principe de la division successive par 2, en affichant les bits du plus significatif au moins significatif (grâce à l'affichage après l'appel récursif).
Explication détaillée
- Cas de base : Si
n == 0, la fonction retourne sans rien afficher. - Appel récursif : Elle s'appelle d'abord récursivement avec
n // 2pour traiter les bits de poids fort. - Affichage : Après le retour de l'appel récursif, elle affiche le bit de poids faible (
n % 2).
fct3(21)
fct3(10)
fct3(5)
fct3(2)
fct3(1)
fct3(0) → retour
print(1 % 2 = 1)
print(2 % 2 = 0)
print(5 % 2 = 1)
print(10 % 2 = 0)
print(21 % 2 = 1)Affichage : 10101 (binaire de 21)
n = 21
10101
Récapitulatif
| Fonction | Fonctionnalité | Exemple |
|---|---|---|
| fct1(x, y) | Retourne (x(x+1)/2) + y | fct1(5, 2) = 17 |
| fct2(n) | Retourne ⌊log₂(n)⌋ | fct2(8) = 3, fct2(15) = 3 |
| fct3(n) | Affiche la représentation binaire de n | fct3(21) affiche "10101" |
- Identifier le cas de base (condition d'arrêt) et ce qu'il retourne.
- Analyser l'appel récursif : comment les paramètres évoluent-ils ?
- Comprendre comment le résultat de l'appel récursif est combiné avec d'autres valeurs.
- Pour les fonctions qui affichent, noter l'ordre des appels et des affichages.
- Tester avec de petites valeurs pour vérifier la compréhension.
- Une fonction récursive s'appelle elle-même jusqu'à atteindre un cas de base.
- La somme des entiers 1+2+...+x peut s'exprimer récursivement comme x + somme(x-1).
- Le logarithme entier compte le nombre de divisions par 2 avant d'atteindre 1.
- La conversion binaire utilise les divisions successives par 2 et les restes.
- L'ordre des opérations (avant ou après l'appel récursif) est crucial pour le résultat.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.