Page d'accueil
encyclopedie-enligne.com en page d'accueil| Page d'accueil |
encyclopedie-enligne.com en page d'accueil |
|||||
| Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées | ||||||
La récursivité est le fait de décrire un processus en faisant appel à ce processus. Plus précisément, les cas
compliqués du processus sont décrits à partir de cas plus simples, les cas les plus simples étant donnés explicitement. La notion
de récursivité a été introduite par la mathématicien américain Stephen Kleene, qui a également introduit les expression régulières.
En mathématiques, on décrit couramment des objets par récursivité (même si ce n'est qu'un cas particulier simple d'application du principe d'induction).
L'exemple classique d'une fonction définie récursivement est la factorielle n! :
En informatique, une fonction qui contient un appel à elle-même est dite récursive. Il faut qu'elle comporte une condition d'arrêt, sinon le programme tourne indéfiniment. Cela permet de trouver une solution élégante et claire, même si ce n'est pas toujours la plus efficace, à certains problèmes - comme celui des Tours de Hanoï ou du tri arborescent. On parle alors d'algorithme récursif. Il existe également la récursivité croisée : c'est-à-dire plusieurs procédures ou fonctions peuvent s'appeler mutuellement.
Des techniques existent pour remplacer une récursivité à gauche ou une récursivité à droite par un processus itératif plus économique. On peut alors définir par exemple une factorielle récursivement, tout en ayant l'assurance qu'au moment de son exécution elle sera exécutée autrement qu'avec de coûteux empilements de contextes d'appel. Voir Haskell.
La récursivité est étudiée par des langages de programmation théoriques comme la Récursion Primitive ou le Système T de Gödel par exemple.
Certains acronymes sont récursifs : le plus connu est bien sûr GNU qui signifie « GNU is Not Unix ».
