Algorithmique & Programmation · NSI LycéeRécursivitéPile d'Appels LIFO & Arbre

Simulateur de Récursivité Pas à Pas

Visualisez le fonctionnement interne de la pile d'appels (Call Stack), l'exécution ligne par ligne du code Python et le déploiement de l'arbre des appels récursifs en temps réel.

Paramètre n =

fib(n) = fib(n - 1) + fib(n - 2) avec fib(0) = 0, fib(1) = 1Exemple classique d'arbre binaire d'appels récursifs à croissance exponentielle.

Ligne active : 1

1▶def fib(n):

2 if n <= 1:

3 return n

4 else:

5 return fib(n - 1) + fib(n - 2)

Appel de fib(4) → empilement sur la pile d'appels.

Console :

(aucune sortie)

Pile d'Appels (1)

LIFO (Last In, First Out)

fib(4)en cours...

Arguments : n = 4

💡 Règle d'or NSI : Le sommet de la pile est toujours résolu en premier. Les fonctions en dessous attendent la valeur de retour.

Étape 1 sur 44

Arbre des Appels Récursifs en temps réel

En cours Résolu En attente

Entraînement Interactif · Épreuves NSI

Maîtrisez la récursivité, le cas de base et la pile d'appels

Score : 0 / 0

Pourquoi toute fonction récursive doit-elle obligatoirement posséder au moins un cas de base ?

Les Concepts & Formules de Récursivité à retenir pour le Bac NSI

1. Le Cas de Base

Condition d'arrêt obligatoire sans appel récursif. Sans elle, le programme plante avec l'erreur RecursionError: maximum recursion depth exceeded.

2. Le Variant de Terminaison

Entier positif strictement décroissant à chaque appel (ex: n - 1) assurant la preuve formelle de terminaison en un nombre fini d'étapes.

3. La Pile d'Appels (LIFO)

Mécanisme Last In, First Out : les contextes d'exécution s'empilent. Le sommet de la pile est résolu en premier pour permettre la phase de remontée.

4. Arbre vs Linéaire

Une récursion simple (Factorielle) a un coût en temps linéaire O(n), tandis qu'une double récursion naïve (Fibonacci) a un coût exponentiel O(2ⁿ).

Voir le cours complet sur la Récursivité