Qu'est-ce que la récursion ?
La récursion (ou récursivité) est une technique de programmation ou une fonction s'appelle elle-meme pour résoudre un problème en le decomposant en sous-problemes plus petits de même nature. Chaque appel récursif traite une version réduite du problème jusqu'à atteindre un cas de base (condition d'arrêt) qui retourne un résultat sans appel récursif supplémentaire.
Anatomie d'une fonction récursive
Toute fonction récursive bien formée comporte deux éléments : le cas de base (condition terminale qui arrête la récursion, par exemple n == 0 pour une factorielle) et le cas récursif (l'appel de la fonction a elle-meme avec un argument modifie qui se rapproche du cas de base). L'absence de cas de base ou un cas récursif qui ne converge pas vers le cas de base provoque une récursion infinie et un stack overflow.
Exemples classiques
La factorielle (n! = n * (n-1)!) est l'exemple le plus simple. La suite de Fibonacci (fib(n) = fib(n-1) + fib(n-2)) illustre le problème de la récursion naive (complexité exponentielle sans memoization). Le tri fusion (merge sort) divise récursivement le tableau en deux moities. Le parcours d'arbres (pre-order, in-order, post-order) est naturellement récursif. Le backtracking (N-queens, Sudoku) explore récursivement toutes les possibilités.
Récursion vs itération
Tout algorithme récursif peut être converti en itératif (et inversement). La récursion est plus elegante et naturelle pour les structures récursives (arbres, graphes, fractales) et les algorithmes diviser-pour-regner. L'itération est plus performante en mémoire (pas d'empilement de frames) et evite les stack overflows. La tail récursion (récursion terminale), ou l'appel récursif est la dernière opération, peut être optimisée par le compilateur en boucle (tail call optimization). Certains langages comme Scheme garantissent cette optimisation, d'autres comme Python ne la font pas.
Memoization et programmation dynamique
La récursion naive sur des problèmes avec des sous-problemes chevauchants (Fibonacci, knapsack) recalcule les mêmes valeurs de nombreuses fois. La memoization (top-down) ajoute un cache pour stocker les résultats déjà calcules. La tabulation (bottom-up) elimine complètement la récursion en remplissant un tableau iterativement. Ces techniques transforment une complexité exponentielle en polynomiale. En Python, le décorateur functools.lru_cache ajoute la memoization automatiquement.