La récursivité

Définition

Un algorithme récursif est un algorithme qui s’appelle lui-même.
Concrètement, il s’agit d’une procédure qui contient un appel conditionnel à elle-même.

Cet appel doit être conditionnel sous peine de provoquer une récursivité infinie.
Pendant son fonctionnement, l’algorithme récursif construit une pile d’adresses de retour.

Ainsi, la factorielle de X peut être définie comme X fois la factorielle de (X-1)
Ce qui suppose un cas trivial pour arrêter l’appel récursif.

Ici, le cas trivial consiste à rendre 1 lorsque X est <= 1, sans provoquer d’appel récursif.

Un algorithme récursif est tout à fait adéquat pour visiter une structure arborescente,
telle qu’un disque dur ou toute autre structure fractale.

Visiter un disque dur consiste à visiter la racine,
ou un répertoire donné, pris pour racine de l’exploration.
Dans le répertoire en cours, on note chaque fichier et chaque répertoire.
Dans la collection de répertoires, on appelle l'algorithme récursif sur chaque répertoire,
qui devient donc la racine de l’exploration suivante.
Le processus recommence un niveau plus bas.

• Un répertoire qui n’a pas de parent s’appelle la racine.
• Un répertoire qui a un parent et des descendants s’appelle un nœud.
• Un répertoire qui n’a pas de descendant s’appelle une feuille.

La récursivité fonctionne en deux temps :

1. Lorsqu’elle empile (avant l’appel récursif)
2. Lorsqu’elle dépile (après l’appel récursif)

Si on note les fichiers après avoir exploré les répertoires, on visite le disque dur en profondeur d’abord.
Si on note les fichiers avant d’explorer les répertoires, on visite le disque dur en largeur d’abord.

En profondeur d’abord

On commence par noter les fichiers des feuilles, puis des nœuds les plus profonds.
On terminera par ceux de la racine.

     function visiter(rep)
     {
      pour chaque répertoire
      {
       visiter (répertoire); // Appel récursif
      }
      pour chaque fichier
      {
       noter (fichier);
      }
     }
    

En largeur d’abord

On commence par visiter les fichers de la racine, puis des nœuds les moins profonds.
On terminera par visiter ceux des feuilles.

     function visiter(rep)
     {
      pour chaque fichier
      {
       noter (fichier);
      }
      pour chaque répertoire
      {
       visiter (répertoire); // Appel récursif
      }
     }
    

Exemple

Cet algorithme récursif visite votre disque dur en largeur d’abord.

L’explorateur