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
Écris une fonction récursive avec mémoïsation pour calculer le nombre de façons de monter un escalier de n marches si tu peux monter 1 ou 2 marches à la fois. Quelle est la complexité sans et avec mémoïsation ?
Corrige cet exercice avec le tuteur →Exercice 2
Implémente un BFS pour trouver le chemin le plus court entre deux nœuds dans un graphe représenté par une liste d'adjacence. Pourquoi BFS et pas DFS ?
Corrige cet exercice avec le tuteur →Cette notion fait partie du chapitre Algorithmique avancée (NSI Terminale).