récursivité

La récursivité est un mécanisme de définition ou de calcul où une entité se réfère à elle-même dans sa propre définition. En mathématiques et en informatique, elle est utilisée pour traiter des problèmes qui se décomposent en versions plus simples du même problème.

En mathématiques, une définition récursive donne d’abord des valeurs de base et ensuite une règle qui permet d’obtenir les termes suivants à partir des termes précédents. Par exemple, une suite peut être définie par F0 et F1, puis Fn = Fn-1 + Fn-2. L’utilisation la plus connue est la suite de Fibonacci. Les définitions récursives sont souvent accompagnées d’un critère d’arrêt, sans quoi l’itération n’aboutit pas.

En informatique, une fonction est dite récursive lorsqu’elle s’appelle elle-même dans son propre corps. Pour assurer l’aboutissement, elle nécessite un ou plusieurs cas de base. Un exemple classique est la fonction factorielle n!, qui peut être définie par n! = n × (n−1)! avec 0! = 1. Les algorithmes récursifs se prêtent bien à la résolution de problèmes naturally divisibles comme les parcours d’arbres et les tris. On distingue la récursivité linéaire et la récursivité terminale (ou tail recursion), qui peut être optimisée par des compilateurs dans certains langages via la réduction de la pile d’appels.

Des variantes existent, comme la récursion mutuelle (plusieurs fonctions s’appellent les unes les autres) ou les définitions récursives d’objets mathématiques et de langages formels. La récursivité offre clarté et simplicité pour les problèmes structurés, mais elle peut entraîner des dépassements de pile si elle n’est pas correctement maîtrisée.