Récursivité
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 ».