Récursivité au Bac NSI : cas de base, appel récursif et terminaison
Mis à jour le · AprenAI
La récursivité compte 5 exercices dans les annales digitalisées de Métropole du Bac NSI (2021, 2022 et 2024), valant de 0,5 à 2 points chacun. Les questions sont courtes et répétitives : définir une fonction récursive, compléter un code à trous, prouver la terminaison ou compter les appels. Il suffit de bien identifier le cas de base et l'appel qui rapproche de ce cas.
- 24 sujets officiels
- 4,8 % des sujets
- 2021-2026 années
Qu'est-ce qu'une fonction récursive en Python ?
Une fonction est récursive quand elle s'appelle elle-même au cours de son exécution. C'est la définition que le Bac demande mot pour mot, et elle rapporte des points : « appel d'une fonction par elle-même ». Pour ne pas boucler à l'infini, une fonction récursive comporte au moins un cas de base, une condition d'arrêt qui renvoie un résultat sans nouvel appel, et un ou plusieurs appels récursifs sur des données plus petites, c'est-à-dire plus proches du cas de base.
La terminaison se prouve avec un variant : une quantité entière qui diminue strictement à chaque appel et qui est minorée. Dans le mélange de Fischer-Yates (Candidats libres 2021, sujet 2), la fonction melange(lst, ind) appelle melange(lst, ind-1) tant que ind est supérieur à 0 : ind est un entier qui décroît de 1 à chaque appel, donc il finit par atteindre 0 et l'appel suivant s'arrête. Pour une liste de longueur n, l'appel initial se fait avec ind = n − 1 et il y a n − 1 appels récursifs, sans compter l'appel initial.
Trois habitudes se retrouvent dans les corrigés. Pour une liste, on appelle la fonction sur la liste privée de son premier élément ou sur une tranche, comme v[1:] ou mot1[1:]. Pour la recherche dichotomique, on appelle la fonction sur la moitié gauche ou droite en conservant des bornes (debut, fin). Pour une exploration d'arbre de décisions, on appelle la fonction deux fois, une fois en prenant l'objet et une fois sans le prendre, puis on garde le meilleur résultat, comme dans la fonction chargeOptimale de Métropole 2024 (sujet 2). Toute fonction récursive peut s'écrire de façon itérative : on remplace l'appel terminal par une boucle, ce qu'on appelle dérécursiver.
- Fonction récursive: Fonction qui s'appelle elle-même au cours de son exécution.
- Cas de base: Condition d'arrêt qui renvoie un résultat sans appel récursif.
- Appel récursif: Appel de la fonction sur une donnée plus petite, qui la rapproche du cas de base.
- Variant: Entier qui décroît strictement à chaque appel et reste minoré : il garantit la terminaison.
- Dérécursiver: Réécrire une fonction récursive sous forme itérative, avec une boucle.
- Recherche dichotomique: Recherche dans une liste triée en divisant l'intervalle par deux à chaque étape.
Quels sujets de Bac sont tombés sur la récursivité ?
Cinq exercices sont rattachés au thème : 2 en 2021, 2 en 2022 et 1 en 2024, soit 3,7 % des exercices digitalisés de la série. Aucun en 2023, 2025 ni 2026. Chaque exercice est une question isolée au sein d'un exercice plus large sur la programmation, avec des barèmes de 0,5 à 2 points. Trois formats se sont succédé.
- Compléter une fonction récursive (3): On donne le squelette et on complète les cas de base et l'appel. Métropole 2022 (sujet 2 de remplacement, 1,25 point) : anagramme(mot1, mot2), avec la fonction enlever(mot, c). Métropole 2022 (sujet 1 de remplacement, 2 points) : définir un appel récursif puis écrire max_surface(v) qui renvoie la villa de plus grande surface. Métropole 2024 (sujet 2, 0,5 point) : compléter chargeOptimale(tab, v_restant, i) pour maximiser le prix d'un chargement de volume limité.
- Prouver la terminaison, compter et tracer (1): Candidats libres 2021 (sujet 2, exercice 4, question 3, 1,25 point) : pourquoi la fonction melange se termine, combien d'appels récursifs pour une liste de longueur n, quels affichages avec les tirages 2, 1, 2 et 0, puis une version itérative.
- Définition et recherche dichotomique récursive (1): Métropole 2021 (sujet 1 de remplacement, exercice 2, partie C, 1,25 point) : donner la définition d'une fonction récursive, puis écrire en Python ou en langage naturel la recherche dichotomique récursive d'un élément dans une liste triée, qui renvoie True ou False.
- Exercice 5 - Question 4 · Métropole 2 remplacement 2022 · Compléter une fonction récursive
- Exercice 2 - Récursivité · Métropole 1 remplacement 2022 · Compléter une fonction récursive
- Exercice 4 - Mélange récursif de Fischer-Yates · Métropole Candidat libre 2021 (sujet 2) · Prouver la terminaison, compter et tracer
- Exercice 2 - Récursivité · Métropole 1 remplacement 2021 · Définition et recherche dichotomique récursive
Entraîne-toi : Récursivité (24 sujets officiels)
Tous les sujets de NSI sur « Récursivité » (2021-2026), avec le corrigé.
Comment compléter une fonction récursive à trous ?
Prenons Métropole 2022 (sujet 2 de remplacement, exercice 5, question 4), où l'on complète anagramme(mot1, mot2). Le squelette comporte trois cas de base et une partie récursive. D'abord, si les deux mots n'ont pas la même longueur, ils ne peuvent pas être des anagrammes : return False. Ensuite, si mot1 est vide, comme les longueurs sont égales, mot2 l'est aussi et toutes les lettres ont été appariées : return True. Troisième cas, si la première lettre de mot1 n'est pas dans mot2, ce n'est pas une anagramme : return False. Dans tous les autres cas, la lettre est présente : on l'enlève de mot2 et on poursuit sur le reste de mot1, avec return anagramme(mot1[1:], enlever(mot2, mot1[0])). À chaque appel, mot1 perd une lettre, donc le cas du mot vide finit par être atteint.
La même logique règle l'exercice max_surface (Métropole 2022, sujet 1 de remplacement) : si la liste v ne contient qu'une villa, on la renvoie (cas de base). Sinon, on compare les surfaces des deux premières villas, on supprime la plus petite et on rappelle la fonction sur la liste raccourcie. Pour chargeOptimale (2024), les corrections complètent len(tab) comme condition d'arrêt, la liste vide comme résultat, puis les deux options : sans la marchandise i (on rappelle avec v_restant et i + 1) et avec elle (on rappelle avec v_restant − tab[i].volume et i + 1), et l'on renvoie option1 si elle rapporte strictement plus que option2, sinon option2.
- Écrivez d'abord le cas de base: Quelle est la plus petite donnée, et que doit renvoyer la fonction dessus ? Liste d'un élément, mot vide, indice égal à len(tab).
- Décrivez l'appel qui rapproche de ce cas: Une tranche mot1[1:], un indice i + 1, un intervalle réduit. Chaque appel doit diminuer la taille de la donnée.
- Combinez le résultat de l'appel: Le résultat renvoyé est-il celui de l'appel (anagramme), un maximum (chargeOptimale) ou une réponse booléenne ? Écrivez le return correspondant.
- Justifiez la terminaison en une phrase: Nommez le variant : « la longueur de mot1 diminue de 1 à chaque appel et atteint 0 ».
- Testez à la main sur un exemple court: Déroulez anagramme('ACTER', 'CARTE') ou max_surface sur deux villas, pour vérifier que les cas de base sont atteints.
- Exercice 5 - Question 4 · Métropole 2 remplacement 2022
- Exercice 2 - Récursivité · Métropole 1 remplacement 2022
- Exercice 2 - Partie C · Métropole 2024 (sujet 2)
À ne pas confondre en récursivité
- Cas de base ≠ Appel récursif: Le cas de base s'arrête et renvoie un résultat. L'appel récursif rappelle la fonction sur une donnée plus petite.
- Récursif ≠ Itératif: Le récursif s'appelle lui-même. L'itératif utilise une boucle for ou while. Les deux sont équivalents, on peut passer de l'un à l'autre.
- Terminaison ≠ Correction: La terminaison dit que la fonction s'arrête (variant). La correction dit qu'elle donne le bon résultat.
- Nombre d'appels ≠ Nombre d'éléments: Pour melange avec n éléments, il y a n − 1 appels récursifs sans compter l'appel initial.
- Tranche v[1:] ≠ Indice i + 1: La tranche crée une nouvelle liste plus courte. L'indice garde la liste et avance dans son parcours. Les deux réduisent le problème.
- randint(a, b) ≠ randrange(a, b): randint inclut les deux bornes a et b. C'est un alias de randrange(a, b + 1).
Mode Bac : ce qui rapporte des points
- Définition: Fonction qui s'appelle elle-même ; elle doit avoir un cas de base pour s'arrêter.
- Variant: Entier qui décroît strictement à chaque appel et reste minoré par 0.
- Appels de melange: n − 1 appels récursifs pour une liste de longueur n.
- Dichotomie: Intervalle vide : False. tab[m] égal à la valeur : True. Sinon, moitié gauche ou droite.
- Squelette d'anagramme: Longueurs différentes : False. mot vide : True. Première lettre absente : False. Sinon appel sur le reste.
- Dérécursiver melange: for ind in range(len(lst) - 1, 0, -1) : tirer j = randint(0, ind), échanger.
Quelles erreurs font perdre des points en récursivité ?
Les corrigés disponibles sont des solutions détaillées sans barème de pénalités. Elles indiquent en revanche ce que la réponse complète doit contenir.
- Oublier le cas de base: Sans condition d'arrêt, la fonction s'appelle à l'infini. Dans la dichotomie, il y a deux cas d'arrêt : intervalle vide et valeur trouvée.
- Appel qui ne rapproche pas du cas de base: Rappeler anagramme(mot1, mot2) sans retirer la lettre ne termine jamais. Il faut mot1[1:] et un mot2 raccourci.
- Mauvaise définition: « Une fonction qui se répète » est insuffisant. La définition attendue est « une fonction qui s'appelle elle-même ».
- Terminaison non justifiée: Dire « parce qu'on arrive à 0 » ne suffit pas. Nommez le paramètre ind, expliquez qu'il décroît de 1 et que ind > 0 devient faux.
- Se tromper d'un appel: Pour n éléments, melange fait n − 1 appels récursifs (valeurs ind de n − 2 à 0). Compter n est une erreur.
- Mal enchaîner les affichages: Dans la trace de melange, un échange avec j égal à ind laisse la liste inchangée (échange d'un élément avec lui-même). L'affichage est alors identique au précédent.
- Inverser option1 et option2: Dans chargeOptimale, option1 est la branche sans la marchandise, option2 celle avec. Le choix final dépend de la comparaison stricte des prix.
Comment réviser la récursivité pour le Bac NSI ?
Peu d'exercices sont rattachés à ce thème, mais la récursivité sert aussi dans les arbres, le diviser pour régner et la programmation dynamique. Bien la maîtriser rapporte sur plusieurs thèmes.
- Apprenez la définition et les trois éléments: Cas de base, appel récursif, variant. Écrivez-les sur une fiche.
- Refaites les quatre exercices de code: anagramme, max_surface, chargeOptimale et la dichotomie récursive, sans regarder la correction.
- Tracez une exécution: Faites tourner melange(lst, 4) avec les tirages 2, 1, 2 et 0 et vérifiez chaque liste affichée.
- Dérécursivez: Transformez melange en boucle for, puis la dichotomie en boucle while.
- Comptez les appels: Pour des fonctions simples, trouvez la formule du nombre d'appels en fonction de n.
Qu'est-ce qu'une fonction récursive ?
C'est une fonction qui s'appelle elle-même au cours de son exécution. Elle doit avoir un cas de base qui arrête la récursion et des appels sur des données plus petites.
Comment prouver qu'une fonction récursive se termine ?
On désigne un variant, c'est-à-dire un entier qui décroît strictement à chaque appel et reste minoré. Pour melange, c'est ind, qui diminue de 1 tant qu'il est supérieur à 0.
Combien d'appels récursifs fait le mélange de Fischer-Yates ?
Pour une liste de longueur n, il y en a n − 1, sans compter l'appel initial fait avec ind = n − 1.
Comment écrire une recherche dichotomique récursive ?
On calcule le milieu m. Si l'intervalle est vide on renvoie False, si tab[m] égale la valeur on renvoie True, sinon on rappelle la fonction sur la moitié gauche ou droite selon la comparaison.
Peut-on remplacer une fonction récursive par une boucle ?
Oui, on dit qu'on dérécursive. Pour melange, une boucle for sur ind de len(lst) − 1 à 1 effectue les mêmes échanges.
Plus sur l'épreuve de NSI
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Arbres et arbres binaires de recherche · 50 sujets
- Graphes : modélisation et parcours · 27 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Programme comme donnée, calculabilité et décidabilité · 2 sujets
- Diviser pour régner · 8 sujets
- Programmation dynamique · 7 sujets
- Recherche textuelle et algorithme de Boyer-Moore · 3 sujets
- Coût des algorithmes, tris et recherche · 23 sujets