NSI Terminale • Programme français, lycées de Montréal

Fiche de révision : récursivité, objet et preuve de programme en NSI

Le chapitre des langages est celui où le code juste ne suffit pas. Les questions demandent de justifier qu'une récursion s'arrête, de compter des appels, de dire pourquoi une classe hérite d'une autre, d'exhiber un invariant. Ce sont des rédactions, pas des programmes, et c'est là que le barème se joue.

Cette fiche liste les neuf erreurs qui reviennent dans les copies, avec la phrase exacte à écrire à la place et ce que chacune coûte au barème.

Le fil du chapitre

Ce chapitre ne demande pas d'écrire du code qui marche, mais de PROUVER ce qu'il fait : terminaison, correction, coût. Un programme juste sans preuve n'y vaut que la moitié des points.

Ce chapitre fait partie de NSI en Terminale

Avant ce chapitre

Cette fiche suppose ces notions acquises. Si une méthode ci-dessous reste opaque, c'est presque toujours l'une d'elles qui manque, pas la fiche.

Algorithmique : recherche, tris, récursivité et complexité Fiche

Remonter plus loin : la chaîne complète (4 chapitres) ↓

Le chemin de remédiation, du plus ancien au plus proche. Un élève qui reprend ce chapitre de zéro le reprend dans cet ordre.

1Algorithmique et PythonSeconde, Mathématiques
2Python : types, contrôle, fonctions et tableauxPremière
3Algorithmique : preuve, terminaison et coûtPremière
4Algorithmique : recherche, tris, récursivité et complexité

L'essentiel

La pile d'appels : ce qui se passe vraiment

• Chaque appel récursif empile un CADRE, avec ses propres variables locales. Rien n'est calculé à la descente.
• Tout se calcule à la REMONTÉE, quand chaque cadre reçoit la valeur renvoyée par celui du dessus.
• Sans cas de base atteignable, la pile déborde : Python lève RecursionError, ce n'est pas une boucle infinie.
• La profondeur maximale est de l'ordre de mille appels : une récursion sur un tableau de dix mille éléments ne passe pas.

Les mêmes trois cadres, lus deux fois : à la descente aucune multiplication n'est faite, à la remontée chacune s'effectue avec la valeur reçue du cadre supérieur.

Une question « quelle est la valeur renvoyée » se traite en dessinant la pile : trois cadres suffisent presque toujours à voir la structure.

Le coût d'une récursivité

• Le nombre d'appels se lit sur l'ARBRE des appels : chaque noeud est un appel, et les sous-arbres identiques sont des calculs refaits.
• Pour la suite de Fibonacci naïve, le nombre d'appels vaut $2F(n+1) - 1$ : quinze appels pour $n = 5$ , deux millions six cent quatre-vingt-douze mille cinq cent trente-sept pour $n = 30$ .
• La mémoïsation range chaque valeur calculée dans un dictionnaire : le nombre d'appels tombe à $2n + 1$ , soit 31 pour $n = 30$ .
• Une récursion terminale, où l'appel récursif est la DERNIÈRE opération, se transforme mécaniquement en boucle.

Objet : ce que le jury attend qu'on nomme

• La classe décrit, l'instance existe. Une classe s'écrit une fois, les instances se comptent.
• self désigne l'instance : $c.methode(x)$ est en réalité $Classe.methode(c, x)$ , ce qui explique pourquoi self est le premier paramètre.
• L'encapsulation est un CONTRAT, pas une barrière : le tiret bas signale qu'un attribut est interne, il n'en interdit pas l'accès en Python.
• Polymorphisme : l'appel $self.aire()$ est résolu à l'EXÉCUTION, selon la classe réelle de l'objet, pas selon celle du code écrit.

On hérite quand la sous-classe peut remplacer la classe parente PARTOUT sans surprendre l'appelant. Sinon, on compose.

Invariant, variant, correction

• INVARIANT : une propriété vraie à chaque tour, qui porte sur le travail DÉJÀ FAIT. Elle sert à la correction.
• VARIANT : un entier positif qui décroît STRICTEMENT à chaque tour. Il sert à la terminaison, et à elle seule.
• Correction partielle : si l'algorithme s'arrête, son résultat est juste. Correction TOTALE : correction partielle plus terminaison.
• Une preuve complète comporte donc trois pièces : l'invariant, sa conservation, et le variant.

Décidabilité

• Le problème de l'arrêt est INDÉCIDABLE : aucun programme ne peut décider, pour tout couple programme-entrée, si l'exécution s'arrête.
• La démonstration est par l'absurde : on construit un programme qui fait le contraire de ce que la méthode prédit sur lui-même.
• Cela n'interdit nullement de prouver la terminaison d'un programme PARTICULIER : c'est la méthode UNIVERSELLE qui n'existe pas.
• Conséquence pratique : aucun outil ne détectera toutes les boucles infinies, ce qui n'empêche aucun outil d'en détecter beaucoup.

Les pièges qui coûtent des points

Les erreurs ci-dessous sont celles que je corrige le plus souvent en séance. Chacune coûte des points sur une copie, même quand le raisonnement est juste.

1. Écrire l'appel récursif avant le cas de base

1 point sur la question de diagnostic, et le vocabulaire est noté

Ce qu'il ne faut pas écrire

« La fonction boucle à l'infini parce que j'ai oublié la condition d'arrêt. »

Ce qu'il faut écrire

« Sans cas de base, la pile déborde et Python lève RecursionError après environ mille appels. Ce n'est pas une boucle infinie, c'est un débordement de pile. »

Pourquoi : Une boucle infinie consomme du temps sans mémoire ; une récursion sans fin consomme de la mémoire et s'arrête d'elle-même sur une erreur. Le sujet distingue toujours les deux.

2. Croire qu'une récursion double coûte comme une boucle

2 points sur la question de coût, celle qui est vraiment notée

Ce qu'il ne faut pas écrire

« La fonction de Fibonacci récursive fait $n$ appels, comme la version itérative fait $n$ tours. »

Ce qu'il faut écrire

« Chaque appel en déclenche deux : l'arbre des appels compte $2F(n+1) - 1$ noeuds, soit 15 pour $n = 5$ et $2\,692\,537$ pour $n = 30$ . La mémoïsation ramène ce nombre à 31. »

L'arbre des appels de fib(5) : le sous-arbre de fib(3) apparaît deux fois et celui de fib(2) trois fois, et c'est cette répétition, non la récursivité, qui coûte cher.

Pourquoi : Ce n'est pas la récursivité qui coûte, c'est la REDONDANCE : les mêmes sous-appels sont refaits un nombre exponentiel de fois. C'est exactement ce que la mémoïsation supprime.

3. Oublier self, ou croire qu'il est passé à l'appel

1 point, et une erreur d'exécution qui bloque la question

Ce qu'il ne faut pas écrire

« $c.aire(2)$ passe un seul argument, donc la méthode s'écrit def aire(x). »

Ce qu'il faut écrire

« $c.aire(2)$ est traduit en $Classe.aire(c, 2)$ : la méthode reçoit deux arguments et s'écrit def aire(self, x). »

Pourquoi : L'instance est passée implicitement en premier argument. Comprendre cette traduction supprime d'un coup toutes les erreurs de nombre d'arguments du chapitre.

4. Croire que le tiret bas empêche l'accès

1 point sur la question de vocabulaire, souvent posée en début de sujet

Ce qu'il ne faut pas écrire

« L'attribut s'appelle _solde, donc il est privé et personne ne peut le modifier de l'extérieur. »

Ce qu'il faut écrire

« Le tiret bas est une CONVENTION : il signale que l'attribut est interne, et Python n'interdit rien. L'encapsulation est un contrat que l'appelant s'engage à respecter. »

Pourquoi : Confondre convention et contrainte fait croire qu'un programme est protégé alors qu'il ne l'est que par discipline. La question du bac porte précisément sur ce statut.

5. Hériter quand la relation est « a un »

2 points sur la question de conception, où le choix doit être justifié

Ce qu'il ne faut pas écrire

« Une voiture a un moteur, donc la classe Voiture hérite de la classe Moteur. »

Ce qu'il faut écrire

« L'héritage traduit « EST UN » : un carré est un rectangle. Une voiture A UN moteur, donc Voiture possède un attribut de type Moteur : c'est de la composition. »

Deux relations, deux schémas : la flèche montante de l'héritage exige un « est un », tandis qu'un « a un » se dessine comme un attribut, jamais comme une flèche d'héritage.

Pourquoi : Le test à appliquer est celui de la substitution : la sous-classe doit pouvoir remplacer la classe parente partout sans surprendre l'appelant. Une voiture ne peut pas remplacer un moteur.

6. Donner un variant à la place d'un invariant

2 points, et la preuve de correction devient impossible à conclure

Ce qu'il ne faut pas écrire

« L'invariant est que $i$ augmente à chaque tour. »

Ce qu'il faut écrire

« Ça, c'est le variant, sous la forme $n - i$ qui décroît. L'invariant porte sur le travail déjà fait : « après $k$ tours, m contient le maximum des $k$ premiers éléments ». »

Pourquoi : Les deux objets prouvent des choses différentes : l'invariant sert à la correction, le variant à la terminaison. Les échanger donne une preuve qui ne démontre rien.

7. Conclure à la correction totale sans parler de terminaison

1 point, systématiquement retiré au bac

Ce qu'il ne faut pas écrire

« L'invariant est conservé et donne le bon résultat en fin de boucle : l'algorithme est correct. »

Ce qu'il faut écrire

« L'invariant établit la correction PARTIELLE. Pour la correction totale, j'ajoute le variant $n - i$ , entier positif qui décroît strictement, donc la boucle s'arrête. »

Pourquoi : Un algorithme qui ne s'arrête jamais vérifie n'importe quel invariant. La terminaison est donc une pièce indépendante de la preuve, et le sujet la demande explicitement.

8. Déduire de l'indécidabilité qu'aucune terminaison n'est démontrable

2 points sur la question de recul, où le contresens est fatal

Ce qu'il ne faut pas écrire

« Le problème de l'arrêt est indécidable, donc on ne peut pas prouver qu'un programme s'arrête. »

Ce qu'il faut écrire

« Aucune méthode UNIVERSELLE n'existe. Pour un programme donné, un variant suffit à prouver la terminaison, et c'est ce qu'on fait à chaque question de ce sujet. »

Pourquoi : L'indécidabilité porte sur l'existence d'un algorithme qui répondrait pour TOUS les cas. Elle ne dit rien de chaque cas particulier, où une preuve à la main reste possible.

9. Ne tester que le cas nominal

1 point sur la question de jeu de tests, qui demande toujours de justifier les cas choisis

Ce qu'il ne faut pas écrire

« La fonction renvoie la bonne valeur sur mon exemple, elle est donc correcte. »

Ce qu'il faut écrire

« Je teste aussi les bords : liste vide, un seul élément, valeurs égales, et la plus grande entrée acceptable. C'est là que se trouvent les erreurs. »

Pourquoi : Un jeu de tests se justifie par ce qu'il COUVRE : chaque cas doit correspondre à une branche du code ou à une frontière de la spécification. Trois cas justifiés valent mieux que dix pris au hasard.

Quelle méthode choisir

Récursif ou itératif, et faut-il mémoïser

La forme des appels : combien d'appels récursifs par exécution, et se recoupent-ils.

Si un seul appel récursif, en dernière opération → récursion terminale, transformable en boucle

Exemple : la somme des éléments d'une liste
Si un seul appel, mais un calcul après → récursion simple, coût linéaire, la pile grandit

Exemple : la factorielle
Si deux appels sur des sous-problèmes DISJOINTS → diviser pour régner, coût en $n \log_{2} n$

Exemple : le tri fusion
Si deux appels sur des sous-problèmes QUI SE RECOUPENT → mémoïsation obligatoire, sinon coût exponentiel

Exemple : Fibonacci, $2\,692\,537$ appels contre 31

c'est le critère qui sépare le raisonnable de l'impraticable

Si la profondeur peut dépasser le millier, la version itérative est obligatoire, quelle que soit l'élégance de la récursion.

Héritage ou composition

La phrase française qui relie les deux classes.

Si « un X EST UN Y » et X peut remplacer Y partout → héritage

Exemple : un carré est un rectangle
Si « un X A UN Y » → composition : un attribut de type Y dans X

Exemple : une voiture a un moteur
Si on veut seulement réutiliser du code → composition, jamais héritage

Exemple : réutiliser une méthode de tri

l'héritage n'est pas un mécanisme de recopie
Si plusieurs classes partagent un comportement à redéfinir → héritage, avec redéfinition et polymorphisme

Exemple : une méthode aire redéfinie par chaque figure

En cas de doute, composer : la composition ne crée aucune dépendance forte, l'héritage en crée une définitive.

La rédaction attendue

Le correcteur coche des étapes. Les voici dans l'ordre, avec la phrase de conclusion qu'il attend mot pour mot.

Prouver qu'une boucle est correcte et qu'elle s'arrête

Quand l'utiliser : L'énoncé demande de justifier qu'un algorithme itératif est correct, ou parle d'invariant.

1 Énoncer l'invariant en une phrase qui porte sur le travail déjà fait, en faisant apparaître le compteur : « après $k$ tours, ... ».
2 Montrer l'initialisation : l'invariant est vrai avant le premier tour, souvent trivialement.
3 Montrer la conservation : s'il est vrai avant un tour, il l'est encore après, en suivant les instructions du corps.
4 Conclure la correction partielle : à la sortie de boucle, l'invariant plus la condition d'arrêt donnent exactement le résultat attendu.
5 Donner le variant : un entier positif qui décroît strictement, donc la boucle s'arrête, ce qui achève la correction totale.

Phrase de conclusion

« Invariant : après $k$ tours, m contient le maximum des $k$ premiers éléments. Il est vrai avant le premier tour, il est conservé car chaque tour compare m au nouvel élément, et à la sortie $k = n$ donne le maximum du tableau entier. Le variant $n - i$ est un entier positif strictement décroissant, donc la boucle s'arrête : l'algorithme est totalement correct. »

Le piège : Écrire un invariant qui ne mentionne pas le compteur : il devient invérifiable et la conservation ne se démontre plus.

Barème : 1 point pour l'énoncé de l'invariant, 1 pour l'initialisation, 1 pour la conservation, 1 pour le variant.

Justifier un jeu de tests

Quand l'utiliser : L'énoncé demande de proposer des tests, ou de dire si un jeu de tests est suffisant.

1 Rappeler la spécification en une phrase : ce que la fonction reçoit, ce qu'elle renvoie, à quelles conditions.
2 Prendre un cas nominal, et dire ce qu'il vérifie.
3 Prendre chaque cas limite de la spécification : entrée vide, un seul élément, valeurs égales, borne maximale.
4 Prendre un cas par branche du code, y compris celles que le cas nominal ne traverse pas.
5 Conclure sur ce que le jeu de tests NE prouve pas : un test ne démontre jamais l'absence de bogue.

Phrase de conclusion

« Le jeu retenu couvre le cas nominal, la liste vide, la liste à un élément et le cas de deux maxima égaux, soit une entrée par branche du code. Il ne démontre pas la correction, qui repose sur l'invariant, mais il exercerait chaque branche au moins une fois. »

Le piège : Aligner cinq tests sans dire ce que chacun couvre : le barème note la justification, pas le nombre.

Barème : 1 point par cas limite justifié, 1 point pour la phrase de portée.

Vérifier avant de rendre

Cinq minutes de vérification récupèrent plus de points qu'un exercice de plus commencé à la hâte.

Dérouler la récursion sur trois niveaux

Écrire les cadres empilés pour un petit argument, puis les valeurs renvoyées à la remontée. Si le cas de base n'apparaît pas, il n'est pas atteignable.

fact(3) doit produire exactement trois cadres et s'arrêter sur fact(1) : quatre cadres signalent un cas de base placé trop bas.
Compter les noeuds de l'arbre des appels

Pour une récursion double, dessiner l'arbre sur un petit argument et compter : si des sous-arbres se répètent, le coût est exponentiel et la mémoïsation est attendue.

L'arbre de fib(5) compte quinze noeuds pour cinq valeurs distinctes : dix appels sont des recalculs.
Tester la substitution avant d'hériter

Se demander si une instance de la sous-classe peut être utilisée partout où le code attend la classe parente, sans surprendre l'appelant. Sinon, composer.

Une voiture ne peut pas remplacer un moteur dans une fonction qui attend un moteur : l'héritage est faux.
Vérifier que le variant est bien un entier positif

Un variant doit être entier, positif ou nul, et décroître STRICTEMENT. Une quantité qui peut stagner un tour ne prouve rien.

$n - i$ convient si $i$ augmente d'au moins 1 par tour ; il ne convient pas si $i$ n'augmente que sous condition.
Relire la spécification avant les tests

Chaque cas limite de la spécification doit avoir son test. Une spécification sans cas limite est probablement incomplète.

Une fonction qui renvoie le maximum d'une liste doit préciser ce qu'elle fait sur une liste vide, sinon aucun test ne peut couvrir ce cas.

L'exercice type décortiqué

Une récursion double, son coût, et la mémoïsation

On écrit la suite de Fibonacci en récursivité naïve, avec $fib(0) = 0$ , $fib(1) = 1$ et $fib(n) = fib(n-1) + fib(n-2)$ .

Dessiner l'arbre des appels pour $n = 5$ , en déduire le nombre d'appels pour $n = 30$ , puis proposer une correction et chiffrer le gain.

Étape 1

L'arbre de $fib(5)$ compte 15 noeuds : $fib(3)$ y apparaît deux fois et $fib(2)$ trois fois.

Pourquoi

Le dessin est la réponse à la moitié de la question : il fait voir que le coût vient de la redondance et non de la récursivité, ce qu'aucune formule seule ne montre.

Étape 2

Le nombre d'appels vérifie $T(n) = 1 + T(n-1) + T(n-2)$ , dont la solution est $T(n) = 2F(n+1) - 1$ .

Pourquoi

La récurrence se lit directement sur la définition : un appel, plus les deux sous-appels. C'est le passage de l'observation à la formule que le barème attend.

Étape 3

Contrôle sur $n = 5$ : $F(6) = 8$ , donc $T(5) = 2 \times 8 - 1 = 15$ , ce qui coïncide avec l'arbre.

Pourquoi

Vérifier la formule sur le cas déjà dessiné coûte une ligne et prouve qu'elle n'a pas été recopiée au hasard. C'est le contrôle le plus rentable de la question.

Étape 4

Pour $n = 30$ : $F(31) = 1\,346\,269$ , donc $T(30) = 2\,692\,537$ appels.

Pourquoi

Le chiffre est ce qui rend la conclusion défendable. « C'est exponentiel » ne vaut rien tant qu'on n'a pas montré ce que cela donne sur une valeur réaliste.

Étape 5

Correction : mémoïsation dans un dictionnaire, consulté avant tout calcul et rempli après.

Pourquoi

Il faut décrire le mécanisme, pas seulement le nommer : consulter AVANT, ranger APRÈS. C'est cet ordre qui garantit qu'aucune valeur n'est calculée deux fois.

Étape 6

Nouveau coût : chaque valeur de 0 à $n$ est calculée une seule fois, soit 31 valeurs pour $n = 30$ , contre $2\,692\,537$ appels.

Pourquoi

Le rapport, de l'ordre de quatre-vingt-six mille, est la réponse chiffrée à « quel gain ». Sans lui, la question reste sans réponse même si la mémoïsation est décrite.

Conclusion rédigée

« La récursivité naïve effectue $T(n) = 2F(n+1) - 1$ appels, soit 15 pour $n = 5$ et $2\,692\,537$ pour $n = 30$ , parce que les mêmes sous-appels sont refaits un nombre exponentiel de fois. En mémoïsant, chaque valeur n'est calculée qu'une fois : 31 valeurs suffisent pour $n = 30$ . »

L'erreur classique sur cet exercice : Répondre « la récursivité est lente » : ce n'est pas la récursivité qui coûte, mais la redondance des sous-appels, et c'est exactement ce que la mémoïsation supprime sans rien changer à la structure récursive.

À savoir par cœur

• À la descente, rien n'est calculé. Tout se fait à la REMONTÉE.
• Pas de cas de base atteignable : RecursionError, pas boucle infinie. Profondeur limitée à environ mille.
• Récursion double sur des sous-problèmes qui se recoupent : mémoïser, sinon coût exponentiel.
• $c.methode(x)$ vaut $Classe.methode(c, x)$ : self est le premier paramètre.
• Le tiret bas SIGNALE, il n'interdit pas. L'encapsulation est un contrat.
• Héritage pour « est un », composition pour « a un ». Test de substitution en cas de doute.
• INVARIANT pour la correction, VARIANT pour la terminaison. Correction totale = les deux.
• Le problème de l'arrêt est indécidable : pas de méthode UNIVERSELLE, mais chaque programme reste prouvable à la main.

Questions fréquentes

Pourquoi ma fonction récursive donne-t-elle une RecursionError ?

Parce que le cas de base n'est jamais atteint : chaque appel en empile un nouveau, et Python limite la profondeur à environ mille cadres. Ce n'est pas une boucle infinie mais un débordement de pile. On vérifie que l'argument décroît strictement à chaque appel et que le cas de base est testé avant tout appel récursif.

Pourquoi Fibonacci en récursif est-il si lent ?

Parce que les mêmes sous-appels sont refaits un nombre exponentiel de fois : l'arbre des appels compte quinze noeuds pour n égal à 5, et deux millions six cent quatre-vingt-douze mille cinq cent trente-sept pour n égal à 30. Ce n'est pas la récursivité qui coûte, mais la redondance. Mémoïser dans un dictionnaire ramène le nombre de valeurs calculées à trente et une.

Quelle différence entre un invariant et un variant de boucle ?

L'invariant est une propriété vraie à chaque tour, qui décrit le travail déjà fait, et il sert à prouver que le résultat est juste. Le variant est un entier positif qui décroît strictement à chaque tour, et il sert uniquement à prouver que la boucle s'arrête. Une preuve complète comporte les deux : c'est ce qu'on appelle la correction totale.

Quand faut-il utiliser l'héritage plutôt que la composition ?

Quand la relation entre les deux classes s'énonce par est un et que la sous-classe peut remplacer la classe parente partout sans surprendre l'appelant. Un carré est un rectangle, donc héritage. Une voiture a un moteur, donc composition : la classe Voiture possède un attribut de type Moteur. Réutiliser du code n'est jamais une raison d'hériter.

Si le problème de l'arrêt est indécidable, peut-on prouver qu'un programme s'arrête ?

Oui, pour un programme donné. L'indécidabilité signifie qu'aucune méthode universelle ne peut répondre pour tout couple programme-entrée, ce qui n'empêche pas de démontrer à la main la terminaison d'un algorithme précis, généralement en exhibant un variant. C'est même exactement ce que demandent les questions de preuve du programme de Terminale.

Passer à la pratique

Exercices corrigés : Récursivité, objet, mise au point et calculabilité

Une méthode se prouve sur une copie, pas sur une fiche. La série du même chapitre reprend chacun de ces pièges dans un exercice, avec le corrigé rédigé étape par étape.

15 exercices corrigés
150 points
255 minutes

Faire les exercices

Fiche précédente Processus, réseaux et sécurisation Fiche suivante Diviser pour régner, programmation dynamique et graphes

Voir aussi

Toutes les fiches Tous les exercices Tutorat NSI NSI : les structures de données NSI : algorithmique et complexité Terminale

Vous cherchez un tuteur en NSI à Montréal ?

Contactez-moi pour une première séance. On reprend les points de méthode qui font perdre des points en évaluation, puis on les met à l'épreuve sur des exercices du niveau réel de l'examen.

Me contacter WhatsApp

Site par Studio Squalli