Qu'est-ce que la recursion ?
La recursion (ou recursivite) est une technique de programmation ou une fonction s'appelle elle-meme pour resoudre un probleme en le decomposant en sous-problemes plus petits de meme nature. Chaque appel recursif traite une version reduite du probleme jusqu'a atteindre un cas de base (condition d'arret) qui retourne un resultat sans appel recursif supplementaire.
Anatomie d'une fonction recursive
Toute fonction recursive bien formee comporte deux elements : le cas de base (condition terminale qui arrete la recursion, par exemple n == 0 pour une factorielle) et le cas recursif (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 recursif qui ne converge pas vers le cas de base provoque une recursion 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 probleme de la recursion naive (complexite exponentielle sans memoization). Le tri fusion (merge sort) divise recursivement le tableau en deux moities. Le parcours d'arbres (pre-order, in-order, post-order) est naturellement recursif. Le backtracking (N-queens, Sudoku) explore recursivement toutes les possibilites.
Recursion vs iteration
Tout algorithme recursif peut etre converti en iteratif (et inversement). La recursion est plus elegante et naturelle pour les structures recursives (arbres, graphes, fractales) et les algorithmes diviser-pour-regner. L'iteration est plus performante en memoire (pas d'empilement de frames) et evite les stack overflows. La tail recursion (recursion terminale), ou l'appel recursif est la derniere operation, peut etre optimisee 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 recursion naive sur des problemes avec des sous-problemes chevauchants (Fibonacci, knapsack) recalcule les memes valeurs de nombreuses fois. La memoization (top-down) ajoute un cache pour stocker les resultats deja calcules. La tabulation (bottom-up) elimine completement la recursion en remplissant un tableau iterativement. Ces techniques transforment une complexite exponentielle en polynomiale. En Python, le decorateur functools.lru_cache ajoute la memoization automatiquement.