Site d’Emmanuel Saint-James
Philologie de la programmation
La récursivité

Le mécanisme de pile est aussi apparu lorsqu’il a fallu calculer une fonction récursive, c’est-à-dire une fonction dont la définition fait appel à elle-même. Voici deux exemples canoniques, définis sur les entiers naturels :

• la factorielle

  Factorielle(0) = 1
  Factorielle(n+1) = (n+1) * Factorielle(n)
  

• la fonction de RózsaPéter

   RózsaPéter(0,p) = p+1
   RózsaPéter(n+1,0) =  RózsaPéter(n,1)
   RózsaPéter(n+1,p+1) =  RózsaPéter(n, RózsaPéter(n+1,p))
  

• à chaque appel il faut mémoriser le calcul à faire au retour, mais cela fait, cette mémorisation est inutile, si bien que la mémoire allouée est aussitôt récupérée ;
• ce mécanisme est donc simple et a fini par être adopté par tous les langages de programmation, après avoir longtemps considéré cet usage comme un snobisme ;
• ce style est appelé programmation fonctionnelle par une traduction approximative de l’anglais, car ne restituant pas le sens de programmation par des fonctions ; cette programmation s’opposant à la programmation impérative, il aurait mieux valu s’inspirer de la grammaire française en l’appelant programmation indicative, ces définitions donnant plutôt des indications qu’une suite d’opérations ;
• certains interprètes ou compilateurs arrivent d’ailleurs à calculer certaines fonctions récursives sans pile ; pour factorielle par exemple, la multiplication étant associative, il est possible de réécrire cette fonction avec un argument supplémentaire et un appel récursif terminal, équivalent au saut en arrière des langages d’assemblage, autrement dit à une boucle ;
• cette dérécursion n’est toutefois pas toujours possible, comme en témoigne la fonction RózsaPéter qui n’a pas de définition non récursive.