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]. Version naïve : complexité exponentielle (recalculs) ; préférer l'itératif pour les grandes valeurs.

Équivalent Python (extrait).
```python
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
Début
Si n = 0 alors Retourner 1
Sinon Si n mod 2 = 0 alors
Retourner Carré(PuissRapide(x, n div 2))
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

TDOL : `i`, `p` entiers. Type/Nature : accumulateur factoriel.

```
DEF FN FactIter(n : entier) : entier
Variables i, p : entier
Début
p ← 1
Pour i de 1 à n faire p ← p * i FinPour
Retourner p
Fin
```

Récursif : lisible ; itératif : moins de pile. On retourne n! ; i dans [1..n].

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