Récursivité
Définition : Définition du Larousse
Propriété que possède une règle ou un élément constituant, de pouvoir se répéter de manière théoriquement indéfinie. (C'est une propriété essentielle des règles d'une grammaire générative, celle qui permet d'engendrer un nombre infini de phrases.)
Qualité d'un programme informatique récursif.
Remarque :
La seconde définition reste énigmatique et pour peu qu'un « programme informatique récursif se caractérise par la mise en œuvre de la récursivité »
, nous voilà bien avancés.
Ne nous contentons pas de cette définition, mais retenons qu'une « définition récursive est une définition dans laquelle intervient ce que l'on veut définir »
.
Une fonction est donc récursive lorsque sa définition fait appel à la fonction elle-même.
Afin que la définition permette la résolution du problème, elle doit intégrer :
Des (ou une) solutions connues associées à des cas triviaux ou simples,
Un moyen d'arriver à ces cas simples en partant d'un cas non trivial.
Pour arriver à ces cas simples du problème, une fonction récursive applique le principe (paradigme) « diviser pour régner ».
Définition : Diviser pour régner
Le paradigme « diviser pour régner » donne lieu à trois étapes à chaque niveau de récursivité :
Diviser : le problème en un certain nombre de sous-problèmes,
Régner : sur les sous-problèmes en les résolvant récursivement ou, si la taille d'un sous-problème est assez réduite, en le résolvant directement,
Combiner : les solutions des sous-problèmes en une solution complète du problème initial.
L'analyse de nombreux problèmes peut révéler une structure récursive où la résolution du problème nécessite la résolution d'un ou plusieurs problèmes similaires de « taille réduite » ; ces derniers étant eux-mêmes décomposables ou se révélant des cas simples.
Conseil :
La première étape de division du principe « diviser pour régner » implique donc de vérifier la nécessité de diviser le problème. Si c'est le cas, nous pouvons poursuivre notre démarche. Dans le cas contraire, nous sommes en présence d'un cas simple qui est traité sans récursivité.
On gardera donc toujours en tête que :
Un appel récursif est toujours précédé d'un test d'arrêt de la récursivité,
Un appel récursif est la résolution d'un sous problème « intermédiaire » entre le problème traité et les (ou le) cas simples.