J’apprends à programmer : les fonctions récursives – la récursivité
<<< Article précédent : Les fonctions
Les fonctions récursives
Et si une fonction s’appelait elle-même ?
Parfois, les fonctions peuvent s’appeler elle-même. Dans ce cas, on appelle cela une fonction récursive. Je vous propose de découvrir par l’exemple dans quels cas cela est utilisé.
Pour faire simple et compréhensible, je vais partir de l’exemple suivant :
« Je veux faire un programme qui va scanner tout mon disque dur à la recherche d’un fichier dont le nom est : ‘monfichier.txt’ « .
Voici l’arborescence que nous allons utiliser :
Comme on peut le voir au-dessus, le fichier recherché est dans le dossier :
D:\Culture-informatique\Dossiers\sousDossier 2
Je vais donc faire une fonction qui recherche un fichier dans l’emplacement que je vais passer en paramètres.
- Si le fichier est trouvé à l’emplacement, alors la fonction affichera l’emplacement trouvé
- Sinon elle renverra une chaîne vide, si le fichier n’est pas trouvé.
Voici la fonction :
(Et je vais écrire la programmation en français pour que cela soit plus lisible).
#début de la fonction
fonction rechecher_fichier (repertoire : chaine)
{
si fichier_existe (repertoire + nomfichier) alors
affiche_message ('fichier trouvé à l'emplacement : '+repertoire)
sinon
si repertoire_trouvé_dans(repertoire) alors
#appel de la fonction récursive en lui passant un repertoire
rechercher_fichier(repertoire + repertoire_trouvé)
fin du si
fin du si
}
#début du programme
rechecher_fichier ('D:\')
#fin du programme
explication de la fonction :
1ère étape :
le début du programme, on appelle la fonction avec le répertoire de base de la recherche : D:\
2ème étape :
la fonction va chercher dans D:\ si le fichier existe.
le fichier n’existe pas mais des répertoires sont trouvés dans D:\, la fonction va donc rechercher dans le répertoire trouvé : « culture-informatique ». Pour chercher le fichier : la fonction va s’appeler en passant en paramètres :
le répertoire d’origine + le répertoire trouvé, soit : D:\Culture-Informatique
3ème étape :
la fonction recherche maintenant dans « D:\Culture-Informatique ». Elle ne trouve pas le fichier recherché mais trouve un dossier appelé : « dossiers ». Elle va donc s’appeler en récursif en utilisant les paramètres suivant : répertoire d’origine (« d:\culture-informatique ») + répertoire à rechercher (« dossier »).
4ème étape :
la fonction recherche maintenant dans « D:\Culture-Informatique\dossiers ». Elle ne trouve pas le fichier recherché mais trouve 2 dossiers appelé : « sousdossier 1 » et « sousdossier 2 ». Elle va donc s’appeler en passant les 2 répertoires, l’un après l’autre.
5ème étape :
la fonction a trouvé le fichier, elle affiche le répertoire.
Important : La sortie
Vous comprendrez facilement qu’une fonction qui s’appelle toute seule doit à un moment sortir car si elle continue à s’appeler, cela va forcément planter. Dans l’exemple ci-dessous, c’est facile car cela va s’arrêter lorsqu’il n’y a plus de répertoire à parcourir mais dans certains cas, il faut forcer la sortie de la fonction.
En fonction des langages
Attention, tous les langages n’autorisent pas les fonctions récursives.
Conclusion
Voila, j’ai rédigé cet article très rapidement pour expliquer le fonctionnement des fonctions récursives car Chanou m’avait laissé un commentaire demandant d’expliquer le fonctionnement de ce type de fonction. J’espère que cela est plus clair.
Retrouvez l’ensemble des articles sur la programmation :
-
Langage de programmation
-
Apprendre la programmation
