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.

Ce qui aide à reconnaître la démarche

« É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 »

Besoin d’un point de départ ? Voir la méthode

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.

Les pièges à vérifier dans ta démarche

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.

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))

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

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

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

1 Drill RV-A.1 — factorielle récursive

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..+∞[.

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

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.

3 Drill RV-A.3 — somme récursive

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..+∞[.

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

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).

5 Drill RV-A.5 — puissance récursive

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..+∞[.

6 Drill RV-A.6 — exponentiation rapide

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..+∞[.

7 Drill RV-A.7 — Fibonacci

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..+∞[.

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

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.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Récursivité — factorielle, PGCD, Fibonacci

Exercice — dans l'esprit des sujets du bac

Changer d’énoncé, garder le raisonnement

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

Drill RV-A.1 — factorielle récursive

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

Drill RV-A.3 — somme récursive

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

Drill RV-A.5 — puissance récursive

Drill RV-A.6 — exponentiation rapide

Drill RV-A.7 — Fibonacci

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

Relier ce raisonnement au bac