Récursivité et méthodes de conception d'algorithmes

Pour réduire la complexité temporelle (ex: passer de $O(n)$ à $O(\log n)$).

💡 À retenir : C'est la base des algorithmes de tri efficaces (Merge Sort).

Oui, car chaque appel crée un nouveau "cadre de pile" (stack frame) qui stocke les variables locales et l'adresse de retour.

💡 À retenir : La récursion profonde peut saturer la mémoire.

Si l'appel récursif est la toute dernière opération effectuée par la fonction, sans calcul supplémentaire après.

💡 À retenir : La récursion terminale permet au compilateur d'optimiser l'espace.

Pas nécessairement. Si elle est bien conçue (notamment avec la récursion terminale ou la mémoïsation), sa performance est comparable à l'itérative. Cependant, l'appel de fonction a un coût système (gestion de la pile).

💡 À retenir : La récursivité est souvent plus lisible, mais l'itération est plus économe en mémoire.

1. Écris l'équation de récurrence : $T(n) = aT(n/b) + f(n)$.
2. Utilise le théorème maître (Master Theorem) pour trouver la classe de complexité.

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

C'est quand la pile d'exécution est pleine. Ça arrive souvent quand le cas de base n'est jamais atteint ou quand la profondeur de récursion est trop grande.

💡 À retenir : Vérifie toujours ta condition d'arrêt avant de lancer le code.

Oui, le backtracking est une technique récursive qui explore systématiquement les solutions possibles et revient en arrière si une branche ne mène pas à une solution.

💡 À retenir : Le backtracking est une exploration d'arbre de recherche.

Oui, théoriquement tout algorithme itératif peut être écrit de manière récursive, mais ce n'est pas toujours efficace ou recommandé.

💡 À retenir : Choisis la récursivité pour les problèmes naturellement récursifs (arbres, graphes).

En utilisant une structure de données explicite (une pile) pour simuler la pile d'appels système.

💡 À retenir : La pile remplace l'appel récursif.

Directe : A appelle A. Indirecte : A appelle B et B appelle A.

💡 À retenir : La logique reste la même, seule la structure change.

Non, le cas de base est la condition où le problème est trivialement résolu. Ça peut être une liste vide, un arbre avec un seul nœud, etc.

💡 À retenir : Le cas de base dépend de la structure de données.

Elle n'est pas obligatoire mais fortement recommandée pour éviter de recalculer les mêmes sous-problèmes (comme dans Fibonacci).

💡 À retenir : Mémoïsation = gain de temps énorme.