Question transversaleMathsNSIRécursivité et récurrence

Pourquoi un programme récursif de quatre lignes met-il des secondes à calculer le 30ᵉ terme de Fibonacci ?

Q: Combien de fois fib(2) est-il appelé pour calculer fib(6) ?

5 fois, soit $F₅$ : en général fib($k$) est appelé $Fₙ₋ₖ₊₁$ fois pour $2≤ k≤ n$.

Q: Que vaut φ, et quel est son lien avec Fibonacci ?

$φ=(1+sqrt5)/2$ ; le rapport $Fₙ₊₁/Fₙ$ tend vers $φ$.

La fonction fib(n) = fib(n − 1) + fib(n − 2) fait A(n) = 2F(n + 1) − 1 appels : 177 pour n = 10, 2 692 537 pour n = 30. Le nombre d'appels croît comme 1,618ⁿ. En mémorisant les résultats, on passe à n appels seulement.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

J'ai programmé la suite de Fibonacci en récursif, comme sa définition. Pour n = 10, le résultat est immédiat ; pour n = 35, j'ai attendu de longues secondes. J'ai voulu comprendre pourquoi une définition si simple donne un programme si lent, et j'ai découvert que le nombre d'appels suit lui-même une suite de Fibonacci.

L'enjeu et les notions du programme

Établir une relation de récurrence sur le nombre d'appels, la résoudre par récurrence et comparer avec la version mémoïsée.

Mathématiques

Suites définies par récurrence, suite de Fibonacci (première)
Raisonnement par récurrence (terminale)
Croissance géométrique, nombre d'or (première)

Numérique et sciences informatiques

Récursivité, arbre des appels (terminale)
Programmation dynamique, mémoïsation (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
La suite de Fibonacci vérifie $F_{0} = 0$ F₀=0, $F_{1} = 1$ F₁=1, $F_{n} = F_{n - 1} + F_{n - 2}$ Fₙ=Fₙ₋₁+Fₙ₋₂. Programmée telle quelle, la fonction s'appelle deux fois à chaque étape. Problématique : combien d'appels fait-elle, et comment l'accélérer ?
2. Mathématiques : compter les appels
4 min
Notons $A (n)$ A(n) le nombre d'appels pour calculer fib( $n$ n). On a $A (0) = A (1) = 1$ A(0)=A(1)=1, et pour $n \geq 2$ n≥2 : $A (n) = 1 + A (n - 1) + A (n - 2)$ A(n)=1+A(n-1)+A(n-2) (l'appel lui-même, plus ceux des deux sous-calculs).
On conjecture $A (n) = 2 F_{n + 1} - 1$ A(n)=2Fₙ₊₁-1 et on le démontre par récurrence forte. Initialisation : $A (0) = 2 F_{1} - 1 = 1$ A(0)=2F₁-1=1 et $A (1) = 2 F_{2} - 1 = 1$ A(1)=2F₂-1=1. Hérédité : $A (n) = 1 + (2 F_{n} - 1) + (2 F_{n - 1} - 1) = 2 (F_{n} + F_{n - 1}) - 1 = 2 F_{n + 1} - 1$ A(n)=1+(2Fₙ-1)+(2Fₙ₋₁-1)=2(Fₙ+Fₙ₋₁)-1=2Fₙ₊₁-1.
Valeurs : $A (10) = 2 \times 89 - 1 = 177$ A(10)=2×89-1=177, $A (30) = 2 \times 1346269 - 1 = 2692537$ A(30)=2×1 346 269-1=2 692 537. Comme $F_{n}$ Fₙ croît à peu près comme $φ^{n}$ φⁿ avec $φ \approx 1, 618$ φ≈1,618, chaque terme supplémentaire multiplie le temps par environ 1,6 : passer de 30 à 40 le multiplie par $φ^{10} \approx 123$ φ¹⁰≈123.
3. NSI : mémoriser pour ne pas recalculer
3 min
L'arbre des appels montre le gaspillage : fib(28) est calculé 2 fois, fib(27) 3 fois, fib(26) 5 fois… On recalcule sans cesse les mêmes valeurs.
Mémoïsation : on stocke chaque résultat dans un dictionnaire ; avant de calculer, on regarde s'il est déjà connu. Chaque fib( $k$ k) n'est alors calculé qu'une fois : environ $n$ n calculs. Une boucle qui garde les deux derniers termes fait de même, avec une mémoire constante. En Python, le décorateur lru_cache réalise cette mémoïsation automatiquement. C'est le principe de la programmation dynamique.
4. Conclusion
1,5 min
La version récursive naïve fait $2 F_{n + 1} - 1$ 2Fₙ₊₁-1 appels, une croissance exponentielle ; en mémorisant, on n'en fait que $n$ n. La même définition mathématique peut donner un programme très lent ou très rapide. J'ouvre sur la formule de Binet, qui donne $F_{n}$ Fₙ directement à l'aide de $φ$ φ.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

A (n) = 1 + A (n - 1) + A (n - 2), A (0) = A (1) = 1 A(n)=1+A(n-1)+A(n-2), A(0)=A(1)=1 A (n) = 2 F_{n + 1} - 1 A (10) = 177 A (30) = 2692537 φ^{10} \approx 123 A(n)=2Fₙ₊₁-1 A(10)=177 A(30)=2 692 537 φ¹⁰\approx123

Conclusion : la réponse à la question

Le nombre d'appels de Fibonacci récursif est lui-même un nombre de Fibonacci, multiplié par 2 : il croît exponentiellement. Mémoriser les résultats ramène le coût à n opérations.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Combien de fois fib(2) est-il appelé pour calculer fib(6) ?

5 fois, soit $F_{5}$ F₅ : en général fib( $k$ k) est appelé $F_{n - k + 1}$ Fₙ₋ₖ₊₁ fois pour $2 \leq k \leq n$ 2≤ k≤ n.

Qu'est-ce qu'une récurrence forte ?

Une récurrence où l'hérédité suppose la propriété vraie pour tous les rangs précédents (ici les deux précédents).

Que vaut φ, et quel est son lien avec Fibonacci ?

$φ = \frac{1 + 5}{2}$ φ=(1+sqrt5)/2 ; le rapport $\frac{F _{n + 1}}{F _{n}}$ Fₙ₊₁/Fₙ tend vers $φ$ φ.

Quel est le coût mémoire de la mémoïsation ?

On stocke n valeurs ; la version itérative n'en garde que deux.

Pourquoi « 1 + » dans la relation de A(n) ?

On compte l'appel courant en plus des appels faits par les deux sous-calculs.

Les pièges qui coûtent des points

Confondre la valeur F(n) et le nombre d'appels A(n).
Oublier l'initialisation double dans la récurrence.
Penser que la récursivité est lente par nature : c'est le recalcul qui coûte.

Revoir les notions

Autres questions : récursivité et récurrence

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →