Démontrez Sₙ = n(n + 1)/2 par récurrence.

Vrai pour $n=0$. Si $Sₙ₋₁=((n-1)n)/2$, alors $Sₙ=((n-1)n)/2+n=(n(n+1))/2$.

Question transversaleMathsNSIRécursivité et récurrence

Pourquoi un programme récursif peut-il « déborder » alors que le même calcul en boucle fonctionne ?

Chaque appel récursif en attente occupe une place dans la pile d'appels. Calculer la somme 1 + 2 + … + n récursivement demande n appels empilés : Python refuse au-delà d'environ 1 000. La boucle n'empile rien, et la formule n(n + 1)/2 ne fait qu'un calcul.

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 écrit une fonction récursive qui additionnait les entiers de 1 à n. Pour n = 100, tout allait bien ; pour n = 5 000, Python a affiché « RecursionError: maximum recursion depth exceeded ». La même somme avec une boucle marchait parfaitement. J'ai voulu comprendre ce que la machine fait réellement lors d'un appel récursif.

L'enjeu et les notions du programme

Comparer trois façons de calculer une somme (récursive, itérative, formule) en mémoire et en temps, et comprendre la structure de pile.

Mathématiques

Somme des termes d'une suite arithmétique (première)
Suites définies par récurrence (première)
Raisonnement par récurrence (terminale)

Numérique et sciences informatiques

Récursivité et pile d'appels (terminale)
Structure de pile : empiler, dépiler (terminale)

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

1. Introduction
1 min
Quand une fonction en appelle une autre, l'ordinateur doit se souvenir de l'endroit où reprendre. Problématique : où garde-t-il cette information, et pourquoi la récursivité peut-elle l'épuiser ?
2. Mathématiques : trois façons de calculer une somme
3,5 min
On veut $S_{n} = 1 + 2 + \dots + n$ Sₙ=1+2+…+n. Définition par récurrence : $S_{0} = 0$ S₀=0 et $S_{n} = S_{n - 1} + n$ Sₙ=Sₙ₋₁+n. Formule directe : $S_{n} = \frac{n ( n + 1 )}{2}$ Sₙ=(n(n+1))/2, démontrée par récurrence ou par l'astuce de Gauss (écrire la somme à l'endroit et à l'envers).
Pour $n = 5000$ n=5 000 : $S_{n} = 12502500$ Sₙ=12 502 500. La formule demande 3 opérations, la boucle $n$ n additions, la récursion $n$ n additions aussi… mais avec un coût caché en mémoire.
3. NSI : la pile d'appels
3,5 min
Quand somme( $n$ n) appelle somme( $n - 1$ n-1), le calcul « $+ n$ + n » est mis en attente : l'appel est empilé dans la pile d'appels, avec ses variables locales. On empile somme(5 000), somme(4 999), …, jusqu'à somme(0), puis on dépile en effectuant les additions. Au plus fort, 5 001 appels sont en attente.
La pile est une zone mémoire de taille limitée ; Python fixe une profondeur maximale d'environ 1 000 pour éviter de saturer la mémoire. D'où l'erreur. La boucle, elle, réutilise les mêmes variables : mémoire constante.
Une pile fonctionne en « dernier entré, premier sorti » : c'est exactement l'ordre des retours d'appels. On peut d'ailleurs transformer toute fonction récursive en boucle en gérant soi-même une pile.
4. Conclusion
1,5 min
La récursion empile un appel en attente pour chaque étape : sa profondeur est limitée par la mémoire. La boucle évite cette pile, et la formule $\frac{n ( n + 1 )}{2}$ (n(n+1))/2 évite même la boucle. Choisir la bonne écriture d'un même calcul, c'est penser à la fois en mathématicien et en informaticien. J'ouvre sur la récursivité terminale, que certains langages optimisent.

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.

S_{0} = 0, S_{n} = S_{n - 1} + n S_{n} = \frac{n ( n + 1 )}{2} S_{5000} = 12502500 S₀=0, Sₙ=Sₙ₋₁+n Sₙ=(n(n+1))/2 S₅₀₀₀=12 502 500 pile : somme (5000) \to somme (4999) \to \dots \to somme (0) (5001 appels en attente) pile : somme (5000)\to somme (4999)\to\dots\to somme (0) (5001 appels en attente )

Conclusion : la réponse à la question

Un programme récursif peut déborder parce que chaque appel en attente occupe la pile. Le même calcul en boucle, ou par la formule, ne rencontre pas cette limite.

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.

Démontrez S_n = n(n + 1)/2 par récurrence.

Vrai pour $n = 0$ n=0. Si $S_{n - 1} = \frac{( n - 1 ) n}{2}$ Sₙ₋₁=((n-1)n)/2, alors $S_{n} = \frac{( n - 1 ) n}{2} + n = \frac{n ( n + 1 )}{2}$ Sₙ=((n-1)n)/2+n=(n(n+1))/2.

Que contient un élément de la pile d'appels ?

Les variables locales de l'appel et l'endroit du programme où reprendre après le retour.

Peut-on augmenter la limite en Python ?

Oui avec sys.setrecursionlimit, mais on risque de saturer la mémoire et de faire planter le programme.

Quelle est la différence entre pile et file ?

Pile : dernier entré, premier sorti. File : premier entré, premier sorti.

Quelle méthode préférer pour S_n ?

La formule, en un nombre constant d'opérations ; la boucle si l'on calcule une somme sans formule connue.

Les pièges qui coûtent des points

Croire que la récursion est plus lente en nombre d'opérations : le problème est la mémoire.
Confondre profondeur de récursion et nombre total d'appels.
Oublier que la formule doit être démontrée avant d'être utilisée.

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 →