La récursivité est une technique de programmation où une fonction s'appelle elle-même pour résoudre un problème en le décomposant en sous-problèmes plus simples. Cette approche permet de traiter des structures de données complexes ou des calculs itératifs de manière élégante et concise.
Dans un algorithme récursif, on distingue généralement deux éléments clés :
- Le cas de base : condition d'arrêt qui permet de sortir de la récursion
- L'appel récursif : la fonction qui s'appelle elle-même avec des paramètres modifiés
Voici un exemple simple de fonction récursive en Python pour calculer le factoriel d'un nombre :
def factoriel(n):
if n == 0 or n == 1: # Cas de base
return 1
else:
return n * factoriel(n - 1) # Appel récursif
La récursivité est particulièrement utile pour parcourir des structures de données arborescentes, comme les arbres binaires ou les systèmes de fichiers. Elle est également employée dans des algorithmes de tri comme le tri rapide (quicksort) ou la résolution de problèmes mathématiques comme les suites de Fibonacci.
Cependant, il faut être vigilant car une récursivité mal maîtrisée peut entraîner une consommation excessive de mémoire ou des boucles infinies. Dans certains cas, une approche itérative peut être plus efficace en termes de performances.