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

Leçons de niveau 13
Une page de Wikiversité, la communauté pédagogique libre.
Début de la boite de navigation du chapitre
Introduction
Icône de la faculté
Chapitre no 1
Leçon : Récursivité dans l'algorithmique et la programmation
Retour auSommaire
Chap. suiv. :Algorithmes récursifs

Exercices :

Introduction
fin de la boite de navigation du chapitre
En raison de limitations techniques, la typographie souhaitable du titre, « Récursivité dans l'algorithmique et la programmation : Introduction
Récursivité dans l'algorithmique et la programmation/Introduction
 », n'a pu être restituée correctement ci-dessus.

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[modifier | modifier le wikicode]

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
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
  2. Présence d'un appel récursif mais avec un paramètre plus petit

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

Algorithme récursif[modifier | modifier le wikicode]

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.


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[modifier | modifier le wikicode]

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
Fin de l'exemple