Récursion terminale

Une fonction à récursivité terminale est une fonction où l'appel récursif est la dernière instruction à être évaluée. Cette instruction est alors nécessairement « pure », c'est-à-dire qu'elle consiste en un simple appel à la fonction, et jamais à un calcul ou une composition. Par exemple, dans un langage de programmation fictif :

fonction récursionTerminale(n) :
  // ...
  renvoie récursionTerminale(n - 1)
fonction récursionNonTerminale(n) :
  // ...
  renvoie n + récursionNonTerminale(n - 1)

récursionNonTerminale() n'est pas une récursion terminale car sa dernière instruction est une composition faisant intervenir l'appel récursif. Dans le premier cas, aucune référence aux résultats précédents n'est à conserver en mémoire, tandis que dans le second cas, tous les résultats intermédiaires doivent l'être. Les algorithmes récursifs exprimés à l'aide de fonctions à récursion terminale profitent donc d'une optimisation de la pile d'exécution.

Lors de la compilation (si elle existe), la récursion terminale peut être transformée en itération, c'est-à-dire en une série d'étapes séquentielles totalement dénuée de toute nature récursive.

La récursion terminale est utilisée principalement dans les langages de programmation fonctionnels pour exprimer un processus itératif dans une forme fonctionnelle récursive (en général très condensée et « élégante »). Les langages de programmation fonctionnels peuvent généralement détecter la récursion terminale et optimiser son exécution en transformant la récursion en itération, économisant ainsi l'espace de la pile d'exécution, comme le montre l'exemple ci-dessous.

Prenons ce programme Scheme comme exemple :

(define (factorielle n)
  (define (iterer n acc)
    (if (<= n 1)
        acc
        (iterer (- n 1) (* n acc))))
  (iterer n 1))

On observe que la fonction iterer s'appelle elle-même à la fin de sa définition. Cela permet à l'interpréteur ou au compilateur de réorganiser l'exécution, qui sans cela ressemblerait à ceci :

call factorielle (3)
 call iterer (3 1)
  call iterer (2 3)
   call iterer (1 6)
   renvoie 6
  renvoie 6
 renvoie 6
renvoie 6

après réorganisation :

call factorielle (3)
 remplace les arguments avec (3 1), jump into « iterer »
 remplace les arguments avec (2 3), re-iterer
 remplace les arguments avec (1 6), re-iterer
 renvoie 6
renvoie 6

L'espace consommé sur la pile d'exécution est proportionnel à l'indentation du code fictif ci-dessus. Tandis qu'il augmente linéairement lors de l'exécution récursive, il reste constant après l'optimisation en itération, diminuant ainsi nettement l'empreinte mémoire.

Cette réorganisation économise de l'espace mémoire car aucun état, sauf l'adresse de la fonction appelante, n'a besoin d'être sauvé sur la pile d'exécution. Cela signifie également que le programmeur n'a pas à craindre l'épuisement de l'espace de pile ou du tas pour des récursions très profondes.

Certains programmeurs utilisant des langages fonctionnels réécrivent du code récursif enveloppé de façon à tirer parti de cette caractéristique. Cela requiert souvent l'utilisation d'un accumulateur (acc dans l'implémentation ci-dessus de factorielle), comme argument de la fonction en récursion terminale.

Certains compilateurs utilisent une technique de réécriture de programme en « continuation passing style » qui automatise la transformation d'une récursion enveloppée en récursion terminale. Associée à l'élimination d'appel terminal, cette technique permet d'optimiser le code produit pour des langages fonctionnels.

Pour finir, voici une version enveloppée de factorielle :

(define (factorielle n)
  (cond ((= n 0) 1)
        (else (* n (factorielle (- n 1))))))

Le résultat de l'appel récursif (factorielle (- n 1)) est utilisé par la fonction *, qui constitue ici l'enveloppe. À cause de cela, le résultat de (factorielle (- n 1)) doit être empilé pour être utilisé par *. On ne peut économiser d'espace de pile.

• Article de Guy Steele : Debunking the "Expensive Procedure Call" Myth or, Procedure Call Implementations Considered Harmful or, Lambda: The Ultimate Goto