Une récursion est le fait de s’appeler soi-même pour une fonction informatique.
On parle alors d'algorithmes récursifs et de fonctions récursives.
Commençons par un exemple tiré du Bourgeois gentilhomme (Acte II Scène IV) de Molière. Le héros, Monsieur Jourdain, veut connaître toutes les manières "galantes" d'écrire un billet. De la phrase Belle Marquise, vos beaux yeux, me font mourir d'amour, il pourrait tirer Vos beaux yeux, belle Marquise, d'amour me font mourir, puis Vos beaux yeux, me font mourir, belle Marquise, d'amour, puis Vos beaux yeux, me font mourir d'amour, belle Marquise et ainsi de suite.
Comment Monsieur Jourdain devrait-il procéder pour engendrer toutes ces permutations ? Le mieux pour lui pour être sûr d'y arriver est d'utiliser un procédé récursif. Tout d'abord on construit toutes les permutations de la phrase vos beaux yeux -- me font mourir -- d'amour; puis, dans ces permutations, on insère en première position, puis en deuxième position, puis en troisième position, puis en quatrième position le morceau de phrase belle Marquise.
L'algorithme est récursif parce qu'il s'invoque lui-même.
Les premiers langages de programmation qui ont introduit la récursivité sont LISP et Algol 60 et maintenant tous les langages de programmation modernes proposent une implémentation de la récursivité. On oppose généralement les algorithmes récursifs aux algorithmes dits impératifs ou itératifs qui s'exécutent sans invoquer ou appeler explicitement l'algorithme lui-même.
Commençons par un exemple tiré du Bourgeois gentilhomme (Acte II Scène IV) de Molière. Le héros, Monsieur Jourdain, veut connaître toutes les manières "galantes" d'écrire un billet. De la phrase Belle Marquise, vos beaux yeux, me font mourir d'amour, il pourrait tirer Vos beaux yeux, belle Marquise, d'amour me font mourir, puis Vos beaux yeux, me font mourir, belle Marquise, d'amour, puis Vos beaux yeux, me font mourir d'amour, belle Marquise et ainsi de suite.
Comment Monsieur Jourdain devrait-il procéder pour engendrer toutes ces permutations ? Le mieux pour lui pour être sûr d'y arriver est d'utiliser un procédé récursif. Tout d'abord on construit toutes les permutations de la phrase vos beaux yeux -- me font mourir -- d'amour; puis, dans ces permutations, on insère en première position, puis en deuxième position, puis en troisième position, puis en quatrième position le morceau de phrase belle Marquise.
L'algorithme est récursif parce qu'il s'invoque lui-même.
Les premiers langages de programmation qui ont introduit la récursivité sont LISP et Algol 60 et maintenant tous les langages de programmation modernes proposent une implémentation de la récursivité. On oppose généralement les algorithmes récursifs aux algorithmes dits impératifs ou itératifs qui s'exécutent sans invoquer ou appeler explicitement l'algorithme lui-même.
Aucun commentaire:
Enregistrer un commentaire