NSI
NSI

Fiche de révision :
La Récursivité

La récursivité est un concept fondamental de la NSI Terminale. Comprendre la structure d'une fonction récursive et ses limites est indispensable pour le bac.

Génère tes propres fiches de NSI en 10 secondes →

Essayer
NSI
Définition de la récursivité
Définition
Une fonction récursive est une fonction qui s'appelle elle-même dans sa définition. Elle résout un problème en le décomposant en sous-problèmes de même nature mais de taille réduite. Tout problème récursif peut être résolu itérativement, et vice-versa.
Question probable
Définissez la récursivité et expliquez son principe avec un exemple.
Réponse
→La récursivité repose sur la décomposition : résoudre P(n) en utilisant la solution de P(n-1) ou P(n/2). Exemple simple : ```python def somme(n): """Somme des entiers de 1 à n.""" if n == 0: return 0 # cas de base return n + somme(n-1) # cas récursif somme(4) = 4 + somme(3) = 4 + 3 + somme(2) = 4 + 3 + 2 + somme(1) = 4 + 3 + 2 + 1 + somme(0) = 4 + 3 + 2 + 1 + 0 = 10 ``` Chaque appel crée un contexte d'exécution empilé dans la pile d'appels.
Mnémotechnique
Récursif = se rappelle soi-même. Décompose P(n) → P(n-1). "Miroirs en face à face = récursion infinie." Toujours un cas de base !
1 / 5
NSI
Structure : cas de base et cas récursif
Définition
Toute fonction récursive correcte doit comporter : (1) un ou plusieurs cas de base (condition d'arrêt, ne fait pas d'appel récursif), et (2) un ou plusieurs cas récursifs (appel récursif avec un argument qui se rapproche du cas de base). Sans cas de base, la récursion est infinie.
Question probable
Quelles sont les deux composantes obligatoires d'une fonction récursive ?
Réponse
→Le cas de base stoppe la récursion. Le cas récursif décompose le problème et rapproche le problème du cas de base. Exemple — factorielle : ```python def factorielle(n): if n == 0: # cas de base return 1 return n * factorielle(n - 1) # cas récursif # factorielle(4) = 4 * factorielle(3) # = 4 * 3 * factorielle(2) # = 4 * 3 * 2 * factorielle(1) # = 4 * 3 * 2 * 1 * factorielle(0) # = 4 * 3 * 2 * 1 * 1 = 24 ``` Le variant (ex. n décroît jusqu'à 0) garantit la terminaison.
Mnémotechnique
Cas de base = arrêt. Cas récursif = avance vers la base. "Base + Récursif = toute fonction récursive." Sans base = infini = erreur.
2 / 5
NSI
Pile d'appels et stack overflow
Définition
Chaque appel récursif empile un nouveau contexte d'exécution (variables locales, adresse de retour) dans la pile d'appels (call stack). La profondeur de récursion est limitée par la taille de la pile (en Python, limite 1000 appels par défaut). Au-delà : RecursionError (stack overflow).
Question probable
Expliquez le rôle de la pile d'appels dans la récursivité et le problème du stack overflow.
Réponse
→Lors d'un appel récursif, le système empile les informations du contexte courant (variables locales, position dans le code) sur la call stack. Chaque appel ajoute un cadre (frame). En Python : ```python factorielle(3) → appelle factorielle(2) # empile contexte n=3 → appelle factorielle(1) # empile contexte n=2 → appelle factorielle(0) # empile contexte n=1 → retourne 1 # dépile ← retourne 1*1=1 # dépile ← retourne 2*1=2 # dépile ← retourne 3*2=6 # dépile ``` Si la profondeur dépasse la limite (sys.getrecursionlimit() 1000), Python lève RecursionError. Solution : augmenter la limite ou convertir en itératif.
Mnémotechnique
Pile = empilement des appels. Plus profond = plus de mémoire. Limite Python 1000. Dépassement = RecursionError. 'Call stack = tour d'Hanoï virtuelle.'
3 / 5
NSI
Exemples classiques
Définition
Factorielle : n! = n (n-1)! (base : 0! = 1). Suite de Fibonacci : fib(n) = fib(n-1) + fib(n-2) (base : fib(0)=0, fib(1)=1). Tours de Hanoï : déplacer n disques de A à C via B, en n appels récursifs — complexité exponentielle O(2ⁿ). Ces trois exemples illustrent les patterns récursifs fondamentaux.
Question probable
Écrivez les fonctions récursives pour la factorielle, Fibonacci et les tours de Hanoï.
Réponse
→```python # Factorielle — O(n) def fact(n): return 1 if n == 0 else n * fact(n - 1) # Fibonacci — O(2^n) naïf (à optimiser avec mémoïsation) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2) # Tours de Hanoï — O(2^n) def hanoi(n, source, destination, auxiliaire): if n == 1: print(f"Déplacer disque 1 de {source} vers {destination}") return hanoi(n - 1, source, auxiliaire, destination) print(f"Déplacer disque {n} de {source} vers {destination}") hanoi(n - 1, auxiliaire, destination, source) ``` Fib naïf recompute les mêmes valeurs → utiliser la mémoïsation pour O(n).
Mnémotechnique
fact(n) = 1 si n=0 sinon . fib(n) = fib(n-1)+fib(n-2). Hanoï : n-1 vers B, n vers C, n-1 de B vers C. 'FFH : Fact-Fib-Hanoï = trio classique.'
4 / 5
NSI
Récursivité vs itération
Définition
Tout algorithme récursif peut être converti en itératif et vice-versa. Récursivité : code élégant et proche de la définition mathématique, mais consomme de la pile d'appels. Itération : plus efficace en mémoire, pas de risque de stack overflow, mais parfois moins lisible.
Question probable
Comparez récursivité et itération. Convertissez la factorielle récursive en version itérative.
Réponse
→```python # Récursif (élégant, O(n) pile) def fact_rec(n): return 1 if n == 0 else n * fact_rec(n - 1) # Itératif (efficace, O(1) mémoire) def fact_iter(n): resultat = 1 for i in range(1, n + 1): resultat *= i return resultat ``` Comparaison : Récursif : code court, proche de la définition, pile O(n). Itératif : pas de pile, mémoire O(1), légèrement plus rapide. Pour Fibonacci, la version récursive naïve est O(2ⁿ) mais l'itérative est O(n). Préférer l'itératif pour les grandes valeurs de n. La mémoïsation (cache des résultats) conserve l'élégance récursive avec la performance itérative.
Mnémotechnique
Récursif = élégant, pile O(n). Itératif = efficace, mémoire O(1). Mémoïsation = le meilleur des deux. 'Pour n grand : itératif ou mémoïsé.'
5 / 5

Génère tes fiches NSI
en 10 secondes

Colle ton cours de NSI. FicheIA génère tes fiches structurées instantanément.

Générer mes fiches →

3 générations gratuites · Sans inscription

À lire aussi — NSI

Les Algorithmes

Voir la fiche →

Les Structures de Données

Voir la fiche →

Les Réseaux Informatiques

Voir la fiche →
Génère tes fiches NSI →

Gratuit · Sans inscription