Comment démontrer qu'une fonction récursive très étrange renvoie toujours 91 ?

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.

Mon professeur de NSI nous a montré une fonction récursive qui s'appelle deux fois imbriquée sur elle-même, et nous a demandé de deviner ce qu'elle renvoie. En la testant, j'ai obtenu 91 pour tous les nombres que j'essayais. J'ai voulu savoir si c'était toujours vrai, et surtout le démontrer, car aucun test ne pouvait couvrir tous les entiers.

L'enjeu et les notions du programme

Démontrer par récurrence un résultat sur une fonction récursive non triviale, en choisissant soigneusement l'ordre de la récurrence.

Le plan de l'exposé en 10 min

1. 1. Introduction

   1 min

   John McCarthy, un pionnier de l'intelligence artificielle, a proposé en 1970 la fonction : $M(n)=n-10$M(n)=n-10 si $n>100$n>100, et $M(n)=M(M(n+11))$M(n)=M(M(n+11)) sinon. Problématique : que renvoie-t-elle, et comment le démontrer pour tous les entiers ?

2. 2. Mathématiques : une récurrence en descendant

   4,5 min

   Pour $n>100$n>100, $M(n)=n-10$M(n)=n-10 : par exemple $M(101)=91$M(101)=91. Montrons que $M(n)=91$M(n)=91 pour tout entier $n\le 100$n≤100.

   Premier bloc, $90\le n\le 100$90≤ n≤100. Alors $n+11\ge 101$n+11≥101, donc $M(n+11)=n+1$M(n+11)=n+1 et $M(n)=M(n+1)$M(n)=M(n+1). Ainsi $M(90)=M(91)=\cdots =M(100)=M(101)=91$M(90)=M(91)=…=M(100)=M(101)=91.

   Hérédité par blocs : supposons $M(k)=91$M(k)=91 pour tout $k$k entre $n+1$n+1 et $100$100, avec $n<90$n<90. Alors $n+11$n+11 est entre $n+1$n+1 et 100 (car $n+11\le 100$n+11≤100), donc $M(n+11)=91$M(n+11)=91 et $M(n)=M(91)=91$M(n)=M(91)=91. On descend ainsi de 89 à $-\infty$-∞ : $M(n)=91$M(n)=91 pour tout $n\le 100$n≤100.

   Le résultat est donc : $M(n)=91$M(n)=91 si $n\le 100$n≤100, et $M(n)=n-10$M(n)=n-10 sinon. La définition récursive tortueuse cache une fonction définie par morceaux très simple.

3. 3. NSI : terminaison et coût

   3 min

   La terminaison n'est pas évidente : l'argument augmente de 11 puis diminue de 10. La preuve par récurrence montre au passage que chaque appel termine. On peut compter les appels en Python : pour $n=0$n=0, la fonction fait 203 appels avant de renvoyer 91.

   Cet exemple sert en informatique à tester les outils de vérification automatique de programmes : un vérificateur doit trouver seul l'invariant « le résultat vaut 91 ». Il montre aussi que les tests suggèrent un résultat, mais que seule la démonstration le garantit.

4. 4. Conclusion

   1,5 min

   La fonction 91 renvoie toujours 91 pour $n\le 100$n≤100 : une récurrence descendante, menée par blocs, le démontre. Choisir le bon sens de la récurrence est la clé. J'ouvre sur la fonction de Syracuse, dont on ne sait toujours pas démontrer qu'elle termine.

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

• Faire une récurrence montante qui utilise des valeurs non encore connues.
• Oublier le premier bloc 90 à 100.
• Confondre tester et démontrer.

Revoir les notions

• Suites : récurrence et limites (Terminale spé maths) →
• Fonctions : généralités (Seconde) →

Autres questions : récursivité et récurrence

• Comment être sûr qu'un programme récursif donne toujours le bon résultat ?
• 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 ?

Toutes les questions maths-nsi →