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.

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.

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é.

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.

  1. É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).
  2. 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.
  3. 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.
  4. Justifiez la terminaison en une phrase: Nommez le variant : « la longueur de mot1 diminue de 1 à chaque appel et atteint 0 ».
  5. 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.

À ne pas confondre en récursivité

Mode Bac : ce qui rapporte des points

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.

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.

  1. Apprenez la définition et les trois éléments: Cas de base, appel récursif, variant. Écrivez-les sur une fiche.
  2. Refaites les quatre exercices de code: anagramme, max_surface, chargeOptimale et la dichotomie récursive, sans regarder la correction.
  3. Tracez une exécution: Faites tourner melange(lst, 4) avec les tirages 2, 1, 2 et 0 et vérifiez chaque liste affichée.
  4. Dérécursivez: Transformez melange en boucle for, puis la dichotomie en boucle while.
  5. 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