Récursivité : principe et pile d'appels en Terminale
Récursivité : principe et pile d'appels, c'est une notion de nsi du chapitre « Algorithmique avancée », au programme de Terminale. Voici le cours, un exemple et de quoi t'entraîner.
Récursivité : principe et pile d'appels : le cours
Une fonction récursive s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus simples. Chaque appel s'empile en mémoire jusqu'à atteindre un cas de base qui arrête la récursion.
Exemple
Chercher un document dans des dossiers imbriqués : tu ouvres un dossier, et si tu trouves d'autres dossiers dedans, tu les ouvres de la même façon jusqu'à trouver le fichier.
À retenir
Toute fonction récursive doit avoir un cas de base pour éviter une boucle infinie et un débordement de pile.
S'entraîner sur récursivité : principe et pile d'appels
Fais l'exercice, puis demande au tuteur de te corriger pas à pas.
Exercice 1
Soit la fonction récursive suivante : ```python def mystere(n): if n == 0: return 1 else: return n * mystere(n - 1) ``` 1. Identifiez le cas de base et le cas récursif. 2. Tracez l'exécution de mystere(4) en dessinant la pile d'appels. 3. Que calcule cette fonction ?
Corrige cet exercice avec le tuteur →Exercice 2
On souhaite implémenter la **recherche dichotomique** sur un tableau trié. 1. Écrivez une fonction récursive `recherche_dichotomique(tab, cible, gauche, droite)` qui retourne l'indice de `cible` dans `tab`, ou -1 si absent. 2. Analysez la complexité temporelle en fonction de la taille n du tableau. 3. Testez avec `tab = [1, 3, 5, 7, 9, 11]` et `cible = 7`.
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).