AcademyGilbak LogoAcademyGilbak

NSI · Terminale

Exercices, QCM et annales officielles du Bac NSI

Fiche d'exercices d'entraînement, TP sur machine, cas de base, pile d'appels, comparaisons temporelles et annales officielles du Bac NSI.

Fiche d'exercices & TP sur Machine

Terminale NSI — Python 3

Ce chapitre regroupe la fiche d'exercices d'entraînement, le TP sur machine (analyse de pile et comparaisons temporelles), les annales officielles du Bac NSI et les QCM interactifs.

1. Fiche d'Exercices d'Entraînement

Exercice

Exercice 1 — Identifier cas de base et cas récursif

Pour chacune des fonctions du cours (factorielle, recherche_dichotomique, est_palindrome, fibonacci), identifier précisément le(s) cas de base et le(s) cas récursif.

Exercice

Exercice 2 — Puissance récursive

Écrire une fonction récursive puissance(base, exposant) qui calcule base ** exposant (avec exposant un entier naturel), sans utiliser l'opérateur **.

Exercice

Exercice 3 — Somme des chiffres

Écrire une fonction récursive somme_chiffres(n) qui renvoie la somme des chiffres d'un entier naturel n (par exemple somme_chiffres(1234) doit renvoyer 10).

Indication : le dernier chiffre de n est n % 10, et le reste est n // 10.

Exercice

Exercice 4 — Inverser une chaîne

Écrire une fonction récursive inverser(chaine) qui renvoie la chaîne inversée, sans utiliser chaine[::-1] ni aucune boucle.

Exercice

Exercice 5 — PGCD (algorithme d'Euclide)

Écrire une fonction récursive pgcd(a, b) qui calcule le plus grand commun diviseur de deux entiers naturels, en utilisant la propriété : pgcd(a, b) = pgcd(b, a % b), avec pgcd(a, 0) = a.

Exercice

Exercice 6 — Trace d'exécution

On donne :

Python
1
2
3
4
def mystere(n):
if n == 0:
return ""
return mystere(n - 1) + str(n)
  1. Sans exécuter le code, donner la valeur de mystere(4).
  2. Combien d'appels récursifs sont effectués au total pour calculer mystere(4) (cas de base inclus) ?
Exercice

Exercice 7 — Terminaison

Pour chacune des fonctions suivantes, dire si elle termine toujours, et si oui, donner un variant qui le justifie ; sinon, expliquer pourquoi elle ne termine pas.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def a(n):
if n <= 0:
return 0
return 1 + a(n - 1)
def b(n):
if n == 0:
return 0
return 1 + b(n + 1)
def c(n):
if n <= 1:
return n
return c(n // 2) + 1
Exercice

Exercice 8 — Récursivité vs itération

  1. Écrire une version itérative de puissance (exercice 2), avec une boucle for.
  2. Pour puissance(2, 100000), laquelle des deux versions (récursive ou itérative) risque de provoquer une erreur en Python ? Pourquoi ?

2. TP sur Machine — Explorer, Tracer, Comparer

Terminale NSI — Python 3 — Durée indicative : 1h30

À retenir / Remarque

Objectifs du TP

  • Écrire plusieurs fonctions récursives sur des types de données variés.
  • Observer concrètement la pile d'appels et ses limites.
  • Comparer expérimentalement le coût d'une version récursive et d'une version itérative.

Partie A — Récursivité sur les nombres et les chaînes

A.1. Écrire une fonction récursive est_croissante(tableau) qui renvoie True si les éléments d'un tableau (liste Python) sont rangés par ordre croissant, False sinon.

Indication : le cas de base peut être un tableau de longueur 0 ou 1 ; le cas récursif compare les deux premiers éléments puis se ramène au reste du tableau.

A.2. Écrire une fonction récursive compte_occurrences(chaine, caractere) qui compte le nombre d'occurrences d'un caractère dans une chaîne.

A.3. Écrire une fonction récursive est_trie_partiellement (bonus) qui vérifie qu'un tableau est trié en ignorant la casse pour des chaînes de caractères.

Partie B — Observer la pile d'appels

B.1. Ajouter des print de trace à la fonction factorielle du cours, pour afficher, à chaque appel, sa profondeur (nombre d'appels imbriqués) et la valeur de n :

Python
1
2
3
4
5
6
7
8
def factorielle_tracee(n, profondeur=0):
print(" " * profondeur + f"appel factorielle_tracee({n})")
if n == 0:
print(" " * profondeur + "-> renvoie 1")
return 1
resultat = n * factorielle_tracee(n - 1, profondeur + 1)
print(" " * profondeur + f"-> renvoie {resultat}")
return resultat

Exécuter factorielle_tracee(5) et observer l'affichage : identifier la phase de descente et la phase de remontée.

B.2. Chercher la profondeur de récursion maximale autorisée par défaut avec sys.getrecursionlimit(). Écrire une fonction qui provoque volontairement une RecursionError, et capturer cette erreur avec un try/except pour afficher un message clair plutôt que de laisser planter le programme.

Partie C — Comparer récursif et itératif

C.1. Écrire une version itérative fibonacci_iteratif(n) de la suite de Fibonacci, en coût linéaire (une seule boucle, sans recalculs redondants).

C.2. À l'aide du module time, comparer les temps d'exécution de fibonacci (récursif naïf, vu en cours) et fibonacci_iteratif pour n = 28. Que constatez-vous ?

C.3. Expliquer, en une phrase, pourquoi la différence est si importante entre les deux versions, en reliant votre réponse au nombre d'appels effectués par la version récursive naïve.

3. Sujets d'Annales Officielles du Baccalauréat NSI

Pour vous entraîner dans les conditions réelles des épreuves écrites du Baccalauréat NSI, voici les sujets officiels portant sur la récursivité :

  • Sujet 1 (2021) — Sujet 1 2021 Exercice 2 : Analyse de fonctions récursives sur les chaînes de caractères et calcul de puissances.
  • Sujet 5 (2021) — Sujet 5 2021 Exercice 4 : Parcours récursif d'un arbre binaire et calcul de la hauteur.
  • Sujet 1 (2022) — Sujet 1 2022 Exercice 1 : Recherche dichotomique récursive dans un tableau trié.
  • Sujet 7 (2022) — Sujet 7 2022 Exercice 1 : Conversion décimal-binaire récursive et tracé de figures fractales (Flocon de Koch).

4. QCM d'Évaluation Finale

Rôle du cas de base

Quelle est la conséquence directe de l'absence de cas de base dans une fonction récursive ?

Preuve de terminaison

Pour prouver qu'une fonction récursive se termine, que doit-on obligatoirement définir ?

Pile d'appels (Call Stack)

Lorsque la fonction fctA appelle la fonction fctB, comment réagit la pile d'exécution ?

Complexité de la suite de Fibonacci naïve

Quelle est la complexité temporelle de la fonction récursive naïve fibonacci(n) = fib(n-1) + fib(n-2) ?

5. Simulateur Interactif en Ligne

À retenir / Remarque

Expérimentation Interactive

Vous pouvez visualiser pas à pas l'empilement et le dépilement de la pile d'appels (factorielle, fibonacci, pgcd, puissances) et explorer l'arbre d'exécution dynamique sur notre simulateur :

Accéder au Simulateur de Récursivité (Pile d'Appels & Arbre)→

Avez-vous compris et assimilé ce cours ?

+50 XP

Étudiez le contenu activement pendant au moins 45 secondes pour pouvoir débloquer la validation au mérite.

Temps d'étude actif :0s / 45s
Chapitre précédentTerminaison et synthèse de la récursivité