RV-ARécursivité

Récursivité — factorielle, PGCD, Fibonacci

Idée directrice

L'énoncé demande d'écrire la version récursive d'une fonction classique (factorielle, PGCD, Fibonacci), de donner sa trace d'exécution sous forme d'arbre d'appels, puis souvent de comparer avec la version itérative. La structure cas de base + appel récursif est le schéma central.

Signature de reconnaissance — l'énoncé se trahit ainsi

« Écrire la version récursive de la fonction factorielle » ; « Donner la trace d'exécution de l'appel récursif … » ; « Écrire la fonction récursive PGCD(a,b) » ; « Écrire la fonction récursive calculant le n-ième terme de Fibonacci »

Sujet principal

Exercice — dans l'esprit des sujets du bac

3 questionsCorrigé masqué

Écrire la fonction récursive Fact(n) calculant $n!$ .
1. Identifier le cas de base et le cas récursif.
2. Donner la trace d'exécution de Fact(4) (arbre d'appels et valeurs retournées).
Écrire la fonction récursive PGCD(a, b) basée sur l'algorithme d'Euclide ( $\pgcd(a,b) = \pgcd(b, a \mod b)$ si $b \neq 0$ , sinon $a$ ). Calculer PGCD(48, 18) en donnant la trace.
Écrire la fonction récursive Fib(n) calculant le n-ième terme de la suite de Fibonacci ( $F_0=0$ , $F_1=1$ , $F_n = F_{n-1}+F_{n-2}$ ).
1. Donner la trace de Fib(5).
2. Expliquer pourquoi la version récursive de Fibonacci est inefficace et proposer une amélioration.

Voir la correction commentéeAprès avoir posé votre démarche

1. Factorielle récursive. Structure : cas de base + appel récursif.

TDOL : paramètre n (Type/Nature : entier ≥ 0) ; pas d'objet local obligatoire.

DEF FN Fact(n : entier) : entier
Début
  Si n = 0 alors Retourner 1
  Sinon Retourner n * Fact(n - 1)
Fin

Trace de Fact(4) :

Fact(4) = 4 × Fact(3)
Fact(3) = 3 × Fact(2)
Fact(2) = 2 × Fact(1)
Fact(1) = 1 × Fact(0) = 1 × 1 = 1

En remontant : On retourne 24.

2. PGCD récursif (Euclide). $\mathrm{PGCD}(a,b)=\mathrm{PGCD}(b,a\bmod b)$ si $b\neq 0$ , sinon $a$ .

DEF FN PGCD(a, b : entier) : entier
Début
  Si b = 0 alors Retourner a
  Sinon Retourner PGCD(b, a mod b)
Fin

Trace PGCD(48, 18) : (48,18)→(18,12)→(12,6)→(6,0). On retourne 6.

3. Fibonacci. $F_0=0$ , $F_1=1$ , $F_n=F_{n-1}+F_{n-2}$ .

DEF FN Fib(n : entier) : entier
Début
  Si n < 2 alors Retourner n
  Sinon Retourner Fib(n-1) + Fib(n-2)
Fin

Cas de base : n dans [0..1].
Trace de Fib(5). Fib(5) = Fib(4) + Fib(3) ; Fib(4) = Fib(3) + Fib(2) ; Fib(3) = Fib(2) + Fib(1) ; Fib(2) = Fib(1) + Fib(0) = 1 + 0 = 1. En remontant : Fib(3) = 1 + 1 = 2, Fib(4) = 2 + 1 = 3, Fib(5) = 3 + 2 = 5. L'arbre d'appels compte 15 nœuds : Fib(3) est calculé deux fois, Fib(2) trois fois, Fib(1) cinq fois.
Inefficacité et amélioration. Chaque appel en engendre deux, d'où un nombre d'appels qui croît comme $F_n$ lui-même : complexité exponentielle. Amélioration : version itérative à deux variables (a ← 0 ; b ← 1 ; Pour i de 2 à n : c ← a+b ; a ← b ; b ← c), en O(n), ou mémorisation des valeurs déjà calculées.

Équivalent Python (extrait).

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)
print(fact(4))

Exercices d'entraînement — une nuance à la fois

Entraînement 01 / 08

Drill RV-A.1 — factorielle récursive

1 questionCorrigé masqué

Écrire une fonction récursive Fact(n) calculant n!.

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : n entier. Type/Nature : entier ≥ 0.

DEF FN Fact(n : entier) : entier
Début
  Si n = 0 alors Retourner 1 Sinon Retourner n * Fact(n-1)
Fin

On retourne n! ; n dans [0..+∞[.

Entraînement 02 / 08

Drill RV-A.2 — condition d'arrêt

1 questionCorrigé masqué

Que se passe-t-il si l'on oublie le cas de base dans une fonction récursive ?

Voir la correction commentéeAprès avoir posé votre démarche

Sans cas de base → débordement de pile. TDOL / Type/Nature : n entier.

DEF FN Mauvaise(n : entier) : entier
Début
  Retourner n * Mauvaise(n-1)  { pas de test d'arrêt }
Fin

Toute récursivité exige un cas de base atteint en un nombre fini d'appels.

Entraînement 03 / 08

Drill RV-A.3 — somme récursive

1 questionCorrigé masqué

Écrire Somme(n) = 1 + 2 + … + n de façon récursive.

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : n entier. Type/Nature : entier ≥ 0.

DEF FN Somme(n : entier) : entier
Début
  Si n = 0 alors Retourner 0 Sinon Retourner n + Somme(n-1)
Fin

On retourne 1+…+n ; n dans [0..+∞[.

Entraînement 04 / 08

Drill RV-A.4 — PGCD récursif (Euclide)

1 questionCorrigé masqué

Écrire PGCD(a, b) par l'algorithme d'Euclide récursif.

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : a, b entiers. Type/Nature : naturels.

DEF FN PGCD(a, b : entier) : entier
Début
  Si b = 0 alors Retourner a Sinon Retourner PGCD(b, a mod b)
Fin

On retourne le PGCD (Euclide).

Entraînement 05 / 08

Drill RV-A.5 — puissance récursive

1 questionCorrigé masqué

Écrire Puiss(x, n) = xⁿ (n entier ≥ 0) récursivement.

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : x réel, n entier. Type/Nature selon l'énoncé.

DEF FN Puiss(x : réel ; n : entier) : réel
Début
  Si n = 0 alors Retourner 1 Sinon Retourner x * Puiss(x, n-1)
Fin

On retourne $x^n$ ; n dans [0..+∞[.

Entraînement 06 / 08

Drill RV-A.6 — exponentiation rapide

1 questionCorrigé masqué

Améliorer le calcul de xⁿ en exploitant la parité de n (exponentiation rapide).

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : x réel, n entier. Type/Nature : exposant ≥ 0.

DEF FN PuissRapide(x : réel ; n : entier) : réel
Variables p : réel
Début
  Si n = 0 alors Retourner 1
  Sinon Si n mod 2 = 0 alors
    p ← PuissRapide(x, n div 2)
    Retourner p * p
  Sinon Retourner x * PuissRapide(x, n-1)
Fin

On retourne $x^n$ en $O(\log n)$ ; n dans [0..+∞[.

Entraînement 07 / 08

Drill RV-A.7 — Fibonacci

1 questionCorrigé masqué

Écrire la version récursive de Fibonacci et indiquer son défaut de complexité.

Voir la correction commentéeAprès avoir posé votre démarche

TDOL : n entier. Type/Nature : entier ≥ 0.

DEF FN Fib(n : entier) : entier
Début
  Si n < 2 alors Retourner n Sinon Retourner Fib(n-1)+Fib(n-2)
Fin

On retourne $F_n$ ; complexité exponentielle (recalculs). n dans [0..+∞[.

Entraînement 08 / 08

Drill RV-A.8 — récursif vs itératif

1 questionCorrigé masqué

Citer un avantage et un inconvénient de la récursivité par rapport à l'itératif.

Voir la correction commentéeAprès avoir posé votre démarche

Idée : la récursivité décrit le problème par lui-même ; l'itératif décrit le calcul pas à pas.

Avantage de la récursivité. Le code suit directement la définition mathématique (Fact(n) = n × Fact(n-1), PGCD(a,b) = PGCD(b, a mod b)) : il est court, lisible et facile à prouver correct.

Inconvénient. Chaque appel empile un contexte : mémoire proportionnelle à la profondeur (débordement de pile pour Fact(100000)), temps perdu dans les appels, et parfois recalculs massifs (Fibonacci naïf, exponentiel). La version itérative de la factorielle, p ← 1 ; Pour i de 1 à n faire p ← p × i, n'a aucun de ces coûts : même résultat, une seule boucle, mémoire constante.

Méthode / Automatismes

Structure d'une fonction récursive : cas de base (arrêt) + appel récursif (réduction du problème).
Factorielle : cas de base n=0 → 1 ; récursif → n × Fact(n-1).
PGCD (Euclide) : cas de base b=0 → a ; récursif → PGCD(b, a mod b).
Fibonacci : deux cas de base (n=0 et n=1) ; récursif → Fib(n-1)+Fib(n-2).
Trace d'exécution récursive : écrire la chaîne d'appels avec indentation, puis les valeurs de retour en remontant.

Pièges classiques

Pièges fréquents : oublier le cas de base (boucle infinie/stack overflow) ; cas de base incorrect (ex : Fact(0)=1 et non 0) ; deux cas de base pour Fibonacci (oublier F0=0) ; confondre mod et div.

Variantes rencontrées : puissance entière récursive Puissance(x,n) ; somme des chiffres d'un entier ; tour de Hanoï (raisonnement récursif).