Analyse de fonctions récursives
Dans cette section, nous allons analyser des fonctions récursives pour comprendre leur comportement et déterminer ce qu'elles calculent. La récursivité est un concept fondamental en algorithmique qui permet d'exprimer élégamment de nombreux algorithmes.
Analyse de fonction récursive - Maximum d'un tableau
Expliquez la fonctionnalité de la fonction suivante :
FONCTION fct1(tab[], n)
x ← -1
SI n = 1 ALORS
RETOURNE tab[0]
SINON
x ← fct1(tab, n-1)
FINSI
SI x > tab[n-1] ALORS
RETOURNE x
SINON
RETOURNE tab[n-1]
FINSI
FINFONCTIONdef fct1(tab, n):
if n == 1:
return tab[0]
else:
x = fct1(tab, n-1)
if x > tab[n-1]:
return x
else:
return tab[n-1]La fonction fct1 reçoit un tableau tab et un entier n (qui représente la taille du tableau considéré). Elle retourne la valeur maximale présente dans les n premiers éléments du tableau.
Explication détaillée
- Cas de base : Si
n == 1, la fonction retournetab[0](le seul élément du tableau). - Appel récursif : Sinon, elle calcule récursivement le maximum des
n-1premiers éléments et stocke le résultat dansx. - Comparaison : Ensuite, elle compare ce maximum partiel
xavec le dernier élémenttab[n-1]et retourne le plus grand des deux.
Pour tab = [3, 7, 2, 9, 1] et n = 5 :
fct1(tab, 5)appellefct1(tab, 4)fct1(tab, 4)appellefct1(tab, 3)fct1(tab, 3)appellefct1(tab, 2)fct1(tab, 2)appellefct1(tab, 1)qui retourne3- Remontée : max(3, 7) = 7; max(7, 2) = 7; max(7, 9) = 9; max(9, 1) = 9
Résultat final : 9
Analyse de fonction récursive - Puissance rapide
Expliquez la fonctionnalité de la fonction suivante :
FONCTION fct2(a, b)
SI b = 0 ALORS
RETOURNE 1
FINSI
SI (b mod 2) = 0 ALORS
RETOURNE fct2(a * a, b / 2)
FINSI
RETOURNE fct2(a * a, b / 2) * a
FINFONCTIONdef fct2(a, b):
if b == 0:
return 1
if b % 2 == 0:
return fct2(a * a, b // 2)
return fct2(a * a, b // 2) * aLa fonction fct2 implémente l'exponentiation rapide (ou exponentiation par élévation au carré). Elle calcule ab (a puissance b) de manière récursive et efficace.
Explication détaillée
- Cas de base : Si
b == 0, la fonction retourne 1 (car a⁰ = 1). - Cas pair : Si
best pair, alors ab = (a²)b/2. On appelle récursivement aveca * aetb // 2. - Cas impair : Si
best impair, alors ab = a × ab-1 = a × (a²)(b-1)/2. On appelle récursivement aveca * aetb // 2, puis on multiplie le résultat para.
Pour a = 2, b = 10 :
fct2(2, 10)→ b pair → appellefct2(4, 5)fct2(4, 5)→ b impair → appellefct2(16, 2)puis multiplie par 4fct2(16, 2)→ b pair → appellefct2(256, 1)fct2(256, 1)→ b impair → appellefct2(65536, 0)puis multiplie par 256fct2(65536, 0)→ retourne 1- Remontée : 1 × 256 = 256; 256 (pas de multiplication car pair); 256 × 4 = 1024
Résultat final : 1024 = 2¹⁰
Cette méthode a une complexité de O(log b), ce qui est beaucoup plus efficace que la méthode naïve qui multiplierait a par lui-même b fois (O(b)).
Récapitulatif
| Fonction | Fonctionnalité | Complexité |
|---|---|---|
| fct1 | Recherche du maximum dans un tableau | O(n) en temps, O(n) en espace (pile récursive) |
| fct2 | Calcul de aᵇ par exponentiation rapide | O(log b) en temps, O(log b) en espace |
- 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.
- 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.
- Le maximum d'un tableau peut s'exprimer récursivement comme le maximum entre le dernier élément et le maximum des précédents.
- L'exponentiation rapide utilise la propriété a2k = (a²)k pour réduire la complexité à O(log n).
- La récursivité a un coût mémoire : chaque appel utilise de la pile.
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.