Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Récursivité
Résumé
La récursivité est une démarche qui fait référence à l'objet même de la démarche à un moment du processus. En d'autres termes, c'est une démarche dont la description mène à la répétition d'une même règle. Ainsi, les cas suivants constituent des cas concrets de récursivité :
décrire un processus dépendant de données en faisant appel à ce même processus sur d'autres données plus « simples » ;
montrer une image contenant des images similaires ;
définir un concept en invoquant ce même concept ;
écrire un algorithme qui s'invoque lui-même ;
définir une structure à partir de l'une au moins de ses sous-structures ;
faire pointer un article de Wikipédia vers lui-même ou vers un article qui, par une succession de pointeurs, pointe vers l'article dont on est parti ; ainsi dans l'article que vous lisez, l'expression « pétition de principe » pointe vers un article qui pointe vers le présent article.
Algorithme récursif
vignette|Un arbre binaire est une structure de données récursive. L’arbre représenté, contenant les neuf éléments {2, 7, 2, 6, 5, 11, 5, 9, 4}, est constitué d’un portant à gauche un arbre à cinq éléments {7, 2, 6, 5, 11} et à droite un arbre à trois élements {5, 9, 4}. Ce dernier est constitué d’un portant à gauche un arbre vide, et à droite un arbre à deux éléments {9, 4}. Ce dernier est constitué d’un portant à gauche un arbre à un élément {4}, et à droite un arbre vide. L’arbre à un élément {4} est constitué d’un portant deux arbres vides.
En informatique, la définition de certaines structures de données, comme les listes ou les arbres, est récursive : elle mentionne le type de données en train d’être défini. Par exemple (voir la figure) un arbre binaire est soit vide, soit un nœud portant deux arbres binaires plus petits.
Par ailleurs, une fonction ou plus généralement un algorithme peut contenir un ou des appels à lui-même, auquel cas il est dit récursif. Ce procédé est en particulier employé pour traiter les structures de données récursives, ainsi que pour réaliser le paradigme algorithmique « diviser pour régner ».
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.