Récursivité dans l'algorithmique et la programmation/Introduction

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

La récursivité c’est l’application de l'adage « Diviser pour régner » à l'algorithmique : pour résoudre un problème d'une taille donnée, on scinde ce problème en plusieurs sous-problèmes plus petits, on recommence avec chacun de ces sous-problèmes jusqu'à ce que tous les petits sous-...-sous-problèmes soient facilement résolubles.

Premiers pas

Soyons un peu plus formels. On dit d'une définition qu'elle est récursive si elle fait appel à elle-même pour se définir. Une telle définition peut sembler se mordre la queue, ne rien pouvoir produire de concret. Il n'en sera rien si la définition est bien construite. C’est dans le domaine mathématique que l’on trouve de nombreuses définitions récursives :

Début de l'exemple

Exemple : définition récursive de la factorielle

${\begin{array}{l r}n!={\begin{cases}1&{\mbox{si }}n=0\\n(n-1)!&{\mbox{si }}n>0\end{cases}}&n\in \mathbb {N} \end{array}}$

Fin de l'exemple

Cet exemple montre les deux caractéristiques principales d'une définition récursive intéressante :

1. Présence d'un cas particulier ne faisant pas un appel à la définition, mais donnant un résultat $n!=1{\mbox{si }}n=0$
2. Présence d'un appel récursif mais avec un paramètre plus petit $n!=n(n-1)!{\mbox{ si }}n>0$

Utiliser une définition récursive est souvent considéré comme élégant, concis et lisible.

Algorithme récursif

Appliquons le même schéma aux algorithmes. Si nous disposons d'un algorithme A qui d'une manière directe fait appel à lui-même, ou d'une manière indirecte appelle un autre algorithme B qui lui appelle A, alors l'algorithme A sera dit récursif. Afin d’être correct, il doit exister au moins un cas dans lequel l'appel récursif ne se fait pas, et ce cas doit se produire.

Définition : Algorithme récursif

Un algorithme est récursif quand dans l'enchaînement des instructions qui le composent, l'une de celles-ci est un appel à ce même algorithme.

Cela donne pour notre exemple de factorielle le pseudocode suivant

Nous retrouvons en ligne 4 la condition d'arrêt : aucun appel récursif n'est mis en œuvre, et en ligne 6 l'appel récursif.

Structure de donnée récursive

Si nous appliquons un schéma récursif à la création de structures de données, nous créons une structure de données récursive. Ces structures deviennent nécessaires dès que l’on a besoin de les agrandir dynamiquement. L'exemple le plus simple est sans doute celui de la liste. On peut implémenter une liste d'objets avec une structure élémentaire comme un tableau. Mais la gestion dynamique d'un tableau peut-être difficile à maintenir. Une liste peut alors être considérée sous une forme récursive, une liste est composée de

1. un élément de la liste
2. une sous-liste d'autres éléments

Début de l'exemple

Exemple

Supposons que nous disposions de la liste de personnes suivante :
Alice, Bob, Charles, Damien

Une manière de représenter cette liste serait un tableau :

Alice

Bob

Charles

Damien

(vide)

(vide)

Un tableau possédant une certaine longueur, il a ici été surdimensionné (2 cases sont vides)

Une autre manière de représenter cette liste serait une liste simplement chaînée :

${\Bigg (}Alice,\circ \mapsto {\bigg (}Bob,\circ \mapsto {\Big (}Charles,\circ \mapsto {\big (}Damien,\circ \mapsto \mathbf {()} \quad {\big )}{\Big )}{\bigg )}{\Bigg )}$

Fin de l'exemple

Structure de donnée récursive

Une structure de donnée S est dite récursive si l'une de ses composantes est aussi une structure de donnée S ou si l'un de ses composantes est une structure de donnée faisant appel à S.