Algorithme récursif - Définition

D'autres fonctions récursives à plusieurs arguments

Parmi les fonctions récursives à deux arguments on trouve la fonction d'Ackermann-Peter. Le pgcd peut aussi être présenté récursivement,

      pgcd(p, q) = si p = 0 alors q               sinon si q = 0 alors p               sinon si q ≤ p alors pgcd(p-q, q)               sinon pgcd(p, q-p)      

de même que les coefficients binomiaux quand ils sont définis par la formule de Pascal.

La fonction de Sudan est une fonction à trois arguments (l'indice n est le troisième argument).

Codage de la factorielle dans différents langages de programmation

La factorielle peut se traduire par le programme suivant en pseudo-code :

factorielle(entier k) :

si k=0

alors renvoyer 1

sinon renvoyer k * factorielle(k-1)

finsi

qui donnerait en Python :

      def factorielle(x):          if x == 0:              return 1          return x * factorielle(x-1)      

en Caml :

      let rec factorielle = function        0 → 1      | n → n * factorielle (n-1);;      

en Prolog :

      factorielle(0,1).      factorielle(N,F):- M is N-1, factorielle(M,R), F is R*N.      

en Pascal :

      function factorielle(n : integer):integer;      begin         if n = 0 then factorielle := 1         else factorielle := n * factorielle(n - 1);      end;      

en Java de façon naïve :

      public int factorial(int n) {        if (n == 0)           return 1;        else           return n * factorial(n - 1);       }      

et en C ou en C++ :

      int factorielle(int n)      {          if (n == 0)               return 1;          else               return n * factorielle(n - 1);      }      

Notons que les algorithmes ci-dessus, écrits dans des langages de programmation comme Java, ne prennent pas en compte le fait que le factoriel croit de manière exponentielle et dépasse rapidement la capacité de stockage des "int". Utiliser un type "long" à la place ne sert qu’à reculer pour mieux sauter : il faut trouver une vraie solution alternative.

Une solution en C consisterait à créer une structure contenant un tableau de unsigned int(struct vlong { uint t[10]; }). Ensuite il faudrait créer un fonction int add(uint a, struct vlong cible) qui permettrait de modifier le tableau de cible pour simuler une addition plutot que d'utiliser +.

La fonction add consiste à parcourir (avec un indice i) le tableau cible de droite à gauche et regarder si cible[i]+a> capacité du type uint : dans les deux cas on fait cible[i]+=a (en effet on utilise des unsigned int donc si on dépasse la capacité, cible[i] ne contiendra que le reste de la division euclidienne de cible[i]+a par la capacité d'un unsigned int) ; dans le cas où la condition précédente est vrai (si cible[i]+a> capacité du type uint), alors on ajoute l'action reporter une unité dans cible[i+1] et on vérifie si cible[i+1] ne dépasse pas la capacité de uint, etc... (c'est une boucle). Pour afficher un tel nombre, il suffira de mettre bout à bout les éléments du tableau de la structure.

La présentation récursive d'un algorithme conduit-elle à un programme moins efficace qu'une présentation itérative ?

La mise en œuvre des algorithmes récursifs nécessite une pile. C'est la difficulté d'implanter cette pile qui a fait dire pendant longtemps que les programmes récursifs étaient moins efficaces que les programmes itératifs, mais la situation a changé. En fait, le débat sur l'opposition récursif et itératif est aussi vieux que l'informatique et les progrès récents de la compilation des langages de programmation fonctionnelle permet moins encore de le trancher qu'autrefois. Voici quelques arguments en faveur de la présentation récursive.

• La présentation récursive permet de présenter simplement des algorithmes beaucoup plus astucieux (et donc plus efficaces) et cela a été admirablement montré par Tony Hoare avec son algorithme de tri rapide.
• Les compilateurs d'aujourd'hui sont tellement astucieux que plus le programme leur est présenté de façon abstraite et sans effets de bord, plus ils peuvent mettre en œuvre leurs optimisations et aboutir à des codes objets efficaces.

La contribution la plus percutante dans ce débat a été celle de John Backus, l'inventeur de Fortran, qui dans de sa conférence invitée lors de la remise de son prix Turing en 1977 a pris clairement le parti de la programmation fonctionnelle, donc de la programmation récursive.