À retenir
- Une fonction qui s'appelle elle-même.
- Nécessite obligatoirement une condition de sortie pour s'arrêter.
- Idéale pour traiter des structures en forme d'arbre.
Une fonction récursive est une fonction qui, pour accomplir sa tâche, s'appelle elle-même avec un paramètre simplifié. C'est un peu comme une poupée russe : pour ouvrir la grande poupée, vous devez d'abord ouvrir la poupée légèrement plus petite qui se trouve à l'intérieur, et ainsi de suite jusqu'à atteindre la toute petite poupée finale qui ne s'ouvre plus.
Étymologie
Vient du latin recurrere signifiant « revenir en arrière ». En informatique, le terme s'est imposé pour décrire des processus qui se répètent en bouclant sur leur propre définition.
Exemples d'usage
- Le calcul de la factorielle : Pour calculer 5!, on multiplie 5 par le résultat de 4!, qui lui-même attend le résultat de 3!, etc.
- L'exploration de dossiers : Pour lister tous les fichiers d'un disque, un programme liste les fichiers d'un dossier, puis s'appelle lui-même pour chaque sous-dossier qu'il rencontre.
Cas d'usage
On l'utilise principalement pour manipuler des structures de données hiérarchiques (comme les dossiers d'un ordinateur ou les éléments d'une page web), pour certains algorithmes de tri complexes (QuickSort, MergeSort) ou pour résoudre des problèmes mathématiques naturellement divisibles en sous-problèmes identiques.
Bonnes pratiques
Il est impératif de définir une condition d'arrêt (ou cas de base) claire. Sans elle, la fonction s'appellera à l'infini et provoquera un plantage du programme appelé Stack Overflow (dépassement de la pile de mémoire).
Synonymes
Antonymes
Conseil
Si vous débutez, dessinez l'exécution de la fonction sur un papier avec une petite valeur (par exemple factorielle de 3) pour visualiser comment les appels s'empilent et se résolvent ensuite en sens inverse.
Questions fréquentes
Quelle est la différence avec une boucle (itération) ?
Une boucle répète une action un nombre de fois défini ou tant qu'une condition est vraie, tandis que la récursion résout un problème en le divisant en versions plus petites de lui-même.
Est-ce que la récursion est plus gourmande en mémoire ?
Oui, généralement, car chaque appel de fonction est stocké dans la 'pile' (stack) de la mémoire vive jusqu'à ce que le dernier appel soit terminé.