Terminale · NSI

Contrôle n°2 — Récursivité et Diviser pour régner

Ce DS porte sur la conception et l'analyse d'algorithmes récursifs, avec un accent sur la stratégie Diviser pour régner.

1h30 · Difficile · 3 exercices · Barème sur 20 points

Entraînement généré par IA — vérification pédagogique complète non acquise.

Ce sujet n’est pas une annale officielle. La présence d’un corrigé ne garantit pas son exactitude. Vérifie les méthodes avec ton cours ; une note d’entraînement n’est pas une note officielle. Signaler une erreur.

La fenêtre d’impression de ton navigateur permet aussi d’enregistrer en PDF. Aucun téléchargement de PDF officiel n’est annoncé ici.

Sujet

Travaille d’abord sans consulter le corrigé. Note tes réponses et les étapes de ton raisonnement.

Exercice 1 — Compréhension d'une fonction récursive (7 points)

Considérez la fonction récursive suivante : python def mystere(n): if n == 0: return 1 else: return n * mystere(n-1) 1. Que calcule cette fonction pour un entier n positif ou nul ? Donnez son nom usuel. 2. Pour l'appel `mystere(4)`, détaillez l'empilement des appels récursifs puis le dépilement et les calculs des valeurs de retour. 3. Quelle est sa complexité en temps et en espace mémoire, en fonction de n ?

Exercice 2 — Conception d'un algorithme Diviser pour régner (9 points)

On vous demande d'écrire une fonction récursive `recherche_max(tab, debut, fin)` qui renvoie la valeur maximale contenue dans la tranche `tab[debut:fin]` (indice `fin` exclu) en utilisant une stratégie Diviser pour régner. La stratégie est la suivante : si la tranche a un seul élément, le renvoyer. Sinon, couper la tranche en deux moitiés (à peu près égales), rechercher le maximum dans chaque moitié, et renvoyer le plus grand des deux. 1. Écrivez cette fonction en Python. 2. Montrez l'arbre des appels récursifs pour le tableau `[3, 7, 2, 9, 1]` avec `debut=0`, `fin=5`. 3. Quelle est la relation de récurrence décrivant sa complexité en temps T(n) ? En déduire sa complexité à l'aide du théorème maître (cas 1).

Exercice 3 — Limites de la récursivité (4 points)

Pourquoi la fonction récursive naïve de calcul du n-ième terme de la suite de Fibonacci (F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)) est-elle considérée comme très inefficace ? Sans faire de code, expliquez le phénomène à l'origine de cette inefficacité et donnez sa complexité en temps.

Corrigé et barème

Le total du barème est de 20 points. Les réponses rédigées admettent plusieurs formulations pertinentes ; compare le raisonnement, pas seulement les mots.

Exercice 1 — Compréhension d'une fonction récursive : 7 points

1. Elle calcule la factorielle de n (n!). 2. Appels : mystere(4) → 4 * mystere(3) → 3 * mystere(2) → 2 * mystere(1) → 1 * mystere(0) → 1. Dépilement : mystere(0)=1 → mystere(1)=1*1=1 → mystere(2)=2*1=2 → mystere(3)=3*2=6 → mystere(4)=4*6=24. 3. Complexité en temps : O(n) (n+1 appels). Complexité en espace : O(n) due à la pile d'appels (n+1 cadres d'activation).

Exercice 2 — Conception d'un algorithme Diviser pour régner : 9 points

1. python def recherche_max(tab, d, f): if f - d == 1: return tab[d] else: milieu = (d + f) // 2 max_gauche = recherche_max(tab, d, milieu) max_droit = recherche_max(tab, milieu, f) return max(max_gauche, max_droit) 2. Arbre : Racine (0,5) → (0,2) et (2,5). (0,2) → (0,1)[3] et (1,2)[7] → max=7. (2,5) → (2,3)[2] et (3,5) → (3,4)[9] et (4,5)[1] → max=9. Racine → max(7,9)=9. 3. T(n) = 2T(n/2) + O(1). a=2, b=2, f(n)=O(1)=O(n^0). On a c=0 et log_b(a)=1. Cas 1 : 0 < 1, donc T(n) = Θ(n^(log_b(a))) = Θ(n^1) = Θ(n).

Exercice 3 — Limites de la récursivité : 4 points

L'inefficacité provient du recalcul multiple des mêmes valeurs. Par exemple, pour calculer F(5), on calcule F(3) et F(4). Pour F(4), on recalcule F(3) et F(2). Ainsi, F(3) est calculé deux fois. Ce phénomène d'explosion exponentielle des appels redondants conduit à une complexité en temps exponentielle, en O(φ^n) où φ est le nombre d'or, environ 1.618.

Comprendre, puis réessayer

Repère une erreur précise, explique ce qui t’a manqué et refais l’exercice sans le corrigé. Reprends la notion dans ton cours avant de passer à un autre sujet.

Planifier une révision · Chercher un autre entraînement

Contrôle n°1 — Structures de données : Piles et Files

Contrôle n°3 — Bases de données et Langage SQL

Contrôle n°4 — Architectures matérielles, Réseaux et Routage