Cours de Informatique – Terminale

Ce chapitre étudie la récursivité : une fonction qui s'appelle elle-même avec un problème plus petit, avec un cas de base qui garantit l'arrêt. On écrit des fonctions récursives (factorielle, puissance, suite de Fibonacci, somme des chiffres, PGCD, dichotomie, tours de Hanoï), on suit la pile d'appels, on compare les coûts et on discute les limites de la récursivité. Tous les programmes ont été…

8 chapitres · exercices corrigés et quiz dans l'application

Programme : les chapitres

Chapitre à lire gratuitement : Algorithmique avancée : récursivité et dichotomie

1. Le principe de la récursivité

Une fonction est récursive si elle s'appelle elle-même. Elle comporte toujours :

• un cas de base (qui s'arrête sans appel récursif) ;
• un appel récursif sur un problème plus petit, qui se rapproche du cas de base.

Exemple : n! = n × (n − 1)! avec 0! = 1.

def fact(n):

if n == 0:

return 1

return n * fact(n - 1)

fact(5) renvoie 120 ; fact(10) renvoie 3 628 800.

Déroulement : fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 6.

2. Pile d'appels et terminaison

Chaque appel est empilé en mémoire en attendant le résultat de l'appel suivant, puis les résultats remontent. Sans cas de base atteint, la récursion ne finit jamais et Python signale une erreur RecursionError (la limite par défaut est d'environ 1 000 appels imbriqués).

Terminaison : il faut une quantité entière positive qui diminue strictement à chaque appel (ici n).

3. Autres exemples

• Somme de 1 à n : somme(n) = n + somme(n − 1), somme(0) = 0. somme(4) renvoie 10 ; somme(100) renvoie 5 050.
• Somme des chiffres : chiffres(n) = n % 10 + chiffres(n // 10) si n ≥ 10. chiffres(2468) renvoie 20.
• Mot inversé : inv(s) = inv(s[1:]) + s[0] ; inv("python") renvoie "nohtyp".
• PGCD d'Euclide : pgcd(a, b) = a si b = 0, sinon pgcd(b, a % b). pgcd(48, 18) renvoie 6 ; pgcd(100, 75) renvoie 25.
• Écriture binaire : binaire(n) = binaire(n // 2) + str(n % 2) ; binaire(13) renvoie "1101".

4. Puissance rapide

Version simple : puiss(a, n) = a × puiss(a, n − 1) : n appels.

Version rapide : si n est pair, a^n = (a^(n/2))^2 ; sinon a^n = a × a^(n−1). Le nombre d'appels est de l'ordre de log2(n). puiss_rapide(3, 13) renvoie 1 594 323 = 3^13.

5. Fibonacci : un piège

def fib(n):

if n < 2:

return n

return fib(n - 1) + fib(n - 2)

Les premiers termes sont 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 et fib(20) = 6 765. Mais le coût explose : calculer fib(10) demande 177 appels et fib(20) en demande 21 891, car les mêmes valeurs sont recalculées. Solutions : une boucle, ou la mémoïsation (stocker les résultats déjà calculés dans un dictionnaire).

6. Dichotomie récursive

def dicho(L, v, g, d):

if g > d:

return -1

m = (g + d) // 2

if L[m] == v:

return m

if L[m] < v:

return dicho(L, v, m + 1, d)

return dicho(L, v, g, m - 1)

Avec T = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91] : dicho(T, 23, 0, 9) renvoie 5 et dicho(T, 7, 0, 9) renvoie −1. Le problème est divisé par deux à chaque appel : environ log2(n) appels (10 pour n = 1 000 ; 20 pour un million).

« Diviser pour régner » : on découpe le problème en sous-problèmes plus petits.

7. Les tours de Hanoï

Pour déplacer n disques de A vers C en utilisant B : déplacer n − 1 disques de A vers B, déplacer le plus grand de A vers C, puis déplacer les n − 1 disques de B vers C. Le nombre de déplacements est 2^n − 1 : 7 pour n = 3, 1 023 pour n = 10, 1 048 575 pour n = 20.

Pour n = 3, les déplacements sont : A→C, A→B, C→B, A→C, B→A, B→C, A→C.

8. Retenir l'essentiel

• Cas de base + appel sur un problème plus petit.
• Pile d'appels ; limite de profondeur ; RecursionError.
• Récursif ou itératif : choisir le plus clair et le plus efficace.
• Fibonacci naïf : coût exponentiel ; dichotomie : coût logarithmique.