Comment être sûr qu'un programme récursif donne toujours le bon résultat ?

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.

En NSI, j'ai écrit une fonction récursive qui calculait la factorielle. Elle marchait sur tous mes tests, mais mon professeur m'a demandé : « Comment sais-tu qu'elle marche pour n = 1 000 000 ? » Je ne pouvais pas tout tester. En terminale, j'ai découvert le raisonnement par récurrence, et j'ai compris qu'il a exactement la même structure qu'une fonction récursive.

L'enjeu et les notions du programme

Montrer que le raisonnement par récurrence et la programmation récursive sont deux faces d'une même idée, et s'en servir pour prouver la correction et la terminaison d'un programme.

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

1. 1. Introduction

   1 min

   Une fonction récursive s'appelle elle-même sur un problème plus petit. Problématique : comment démontrer qu'elle calcule ce qu'on attend, pour toutes les entrées, sans pouvoir les tester toutes ?

2. 2. Mathématiques : la récurrence

   3,5 min

   On veut montrer une propriété $P(n)$P(n) pour tout entier $n\ge 0$n≥0. Initialisation : $P(0)$P(0) est vraie. Hérédité : si $P(n-1)$P(n-1) est vraie, alors $P(n)$P(n) l'est aussi. On conclut que $P(n)$P(n) est vraie pour tout $n$n, comme une chaîne de dominos.

   La factorielle se définit elle-même par récurrence : $0!=1$0!=1 et $n!=n\times (n-1)!$n!=n×(n-1)!. On peut aussi démontrer par récurrence des propriétés comme $n!\ge 2^{n-1}$n!≥2ⁿ⁻¹ pour $n\ge 1$n≥1 : vrai pour $n=1$n=1 ; si $(n-1)!\ge 2^{n-2}$(n-1)!≥2ⁿ⁻², alors $n!=n(n-1)!\ge 2\times 2^{n-2}=2^{n-1}$n!=n(n-1)!≥2×2ⁿ⁻²=2ⁿ⁻¹ car $n\ge 2$n≥2.

3. 3. NSI : prouver la fonction

   3,5 min

   La fonction : si $n=0$n=0, renvoyer 1 ; sinon renvoyer $n\times \text{fact}(n-1)$n× fact (n-1). On note $P(n)$P(n) : « fact(n) renvoie $n!$n! ».

   Initialisation : fact(0) renvoie 1, qui vaut $0!$0!. Hérédité : supposons que fact($n-1$n-1) renvoie $(n-1)!$(n-1)!. Alors fact($n$n) renvoie $n\times (n-1)!=n!$n×(n-1)!=n!. La fonction est correcte pour tout $n\ge 0$n≥0.

   Terminaison : chaque appel diminue $n$n de 1, et un entier positif ne peut diminuer indéfiniment ; on atteint 0, le cas de base. Si l'on appelait fact($-1$-1), on descendrait sans fin : la preuve suppose $n\ge 0$n≥0, d'où l'intérêt d'une assertion qui vérifie l'entrée. Un oubli du cas de base correspond à une récurrence sans initialisation : rien n'est démontré.

4. 4. Conclusion

   1,5 min

   Un programme récursif se prouve par récurrence : le cas de base est l'initialisation, l'appel récursif est l'hérédité. Cette preuve couvre toutes les entrées, là où les tests n'en couvrent que quelques-unes. J'ouvre sur les langages de preuve, comme Coq, qui vérifient ces démonstrations automatiquement.

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.

Conclusion : la réponse à la question

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.

Les pièges qui coûtent des points

• Confondre test et preuve.
• Oublier de démontrer la terminaison.
• Écrire une hérédité qui suppose ce qu'on veut démontrer.

Revoir les notions

• Suites : récurrence et limites (Terminale spé maths) →
• Algorithmique et Python (Terminale spé maths) →

Autres questions : récursivité et récurrence

• Pourquoi un programme récursif de quatre lignes met-il des secondes à calculer le 30ᵉ terme de Fibonacci ?
• Pourquoi un programme récursif peut-il « déborder » alors que le même calcul en boucle fonctionne ?
• Comment une figure dessinée par un programme récursif peut-elle avoir une aire nulle et une infinité de triangles ?
• De combien de façons peut-on monter un escalier en faisant des pas d'une ou deux marches ?

Toutes les questions maths-nsi →