Développement

La récursivité est un outil extrêmement puissant pour la description des algorithmes, elle permet de les exprimer facilement, de manière concise, de prouver leur validité et de les évaluer.

Définition:

Un objet est dit récursif s’il est réutilisé directement ou indirectement dans sa définition : on définit aussi bien une structure de données récursive (structure de liste, d’arbre, … ) qu’une action paramétrée récursive.

Généralement la solution d'un problème concret est complexe et longue. La tentative de le résoudre en une seule phase peut conduire à un échec. Pour résoudre facilement et sûrement tel problème on le décompose en sous problèmes plus simples, plus ou moins indépendants. La solution complète du problème sera alors composée des solutions partielles des différents sous problèmes.