Récursifs

Récursifs, ou récursives, qualifie un procédé ou une définition qui fait appel à lui-même pour être résolu ou décrit. En mathématiques et en informatique, une construction récursive s'appuie sur une règle appliquée à un cas plus simple du même problème, jusqu'à atteindre une base résolue.

En mathématiques, une définition récursive précise un état initial et une règle de progression reliant un terme à des termes antérieurs ou à des instances plus petites du problème. Les suites et les récurrences utilisent des conditions d'arrêt pour éviter les boucles infinies.

En informatique, une fonction récursive est une fonction qui s'appelle elle-même pour résoudre le problème. Elle doit comporter un cas de base, qui arrête la récursion, et un ou plusieurs cas récursifs qui rapprochent la solution. Exemples simples: le calcul de la factorielle ou de la suite de Fibonacci.

Types et considérations: la récursion peut être directe ou indirecte; la récursion terminale est optimisée dans certains langages pour éviter l'empilement d'appels; les récursions profondes peuvent entraîner un dépassement de pile et des coûts supplémentaires.

Applications: tri et parcours d'arbres, calcul de suites récurrentes, division et conquête, génération de fractales et analyse syntaxique ou parsing de langages. La récursivité est aussi liée à des notions comme les algorithmes backtracking et les méthodes de programmation fonctionnelle.

Historique et notions connexes: la récursivité est un concept central en mathématiques et en informatique, introduit par leurs fondateurs et développé avec la théorie des algorithmes et des structures. Dans la linguistique, la récursivité décrit l'imbrication des phrases; en informatique, elle est souvent remplacée par l’itération lorsque cela est nécessaire.