Récursivité

Non, au contraire. En Python, la récursivité est souvent plus lente et consomme plus de mémoire à cause de la gestion de la pile d'appels (stack frames). Une boucle for ou while est généralement plus efficace en termes de performance. On utilise la récursivité pour la clarté du code ou quand le problème est naturellement récursif (ex: arbres).

💡 À retenir : La récursivité privilégie la lisibilité, la boucle privilégie la performance.

C'est une erreur qui arrive quand tu dépasses la limite de profondeur de récursion autorisée par Python (généralement 1000 appels). Ça veut dire que ton programme est "bloqué" dans une boucle infinie d'appels récursifs parce que tu as oublié le cas de base ou que ta condition d'arrêt n'est jamais atteinte.

💡 À retenir : Vérifie toujours si ton cas de base est bien défini et accessible.

Pour calculer la complexité, on utilise souvent une relation de récurrence :

1. Identifie le nombre d'appels (ex: $T(n) = T(n-1) + 1$).
2. Résous l'équation pour trouver la forme fermée.
3. Pour la factorielle, c'est $O(n)$ car il y a $n$ appels. Pour Fibonacci récursif simple, c'est $O(2^n)$.

💡 À retenir : La complexité dépend du nombre d'appels et du travail effectué à chaque étape.

Oui, théoriquement, tout algorithme itératif peut être transformé en algorithme récursif. Cependant, ce n'est pas toujours recommandé car cela peut rendre le code plus complexe à lire et plus gourmand en mémoire.

💡 À retenir : La récursivité est un outil puissant, mais utilise-le seulement quand c'est nécessaire.

Non. Si l'appel est la toute dernière opération, on appelle ça la "récursion terminale" (tail recursion). Mais tu peux avoir des appels récursifs au milieu du code, avant ou après d'autres instructions.

💡 À retenir : L'emplacement de l'appel change l'ordre des calculs.

Utilise un schéma en arbre ou une pile :

1. Écris l'appel initial en haut.
2. Dessine des flèches vers les appels suivants.
3. Quand tu atteins le cas de base, remonte les valeurs vers le haut.

💡 À retenir : La pile d'appels fonctionne en "dernier entré, premier sorti" (LIFO).

Oui, très utile pour parcourir des structures complexes ou des listes imbriquées. Tu peux traiter le premier élément (tête) et appeler la fonction sur le reste de la liste (queue).

💡 À retenir : La récursion sur liste est une base de la programmation fonctionnelle.

C'est souvent parce que tu as oublié le mot-clé return devant l'appel récursif. Si tu écris f(n-1) au lieu de return f(n-1), la valeur calculée est perdue.

💡 À retenir : Chaque étape de la récursion doit transmettre le résultat vers le haut.

Oui, c'est très courant, par exemple dans l'algorithme de Fibonacci : return fib(n-1) + fib(n-2). Cela crée un arbre d'appels.

💡 À retenir : Plusieurs appels augmentent souvent la complexité de façon exponentielle.

Oui, c'est une notion fondamentale en algorithmique pour les classes préparatoires et le programme d'informatique. C'est un sujet classique des épreuves.

💡 À retenir : Maîtrise bien la structure cas de base / cas récursif.

Si le problème se définit par lui-même (ex: factorielle, PGCD, parcours d'arbre), la récursivité est naturelle. Si tu dois juste répéter une action simple sur une liste, une boucle est souvent préférable.

💡 À retenir : Choisis la récursivité pour la clarté mathématique.

Oui, chaque appel récursif occupe une place dans la pile d'appels. Si la profondeur est trop grande, tu auras une erreur de mémoire.

💡 À retenir : Attention à la profondeur de récursion pour les grandes données.