Récursion terminale - méthode pour transformer, dans un programme, une récursion en itération

    <p class=default>
      
        La récursion terminale est une méthode pour transformer, dans un programme, une récursion 
        en itération : elle s'applique lorsque l'appel récursif dans une fonction est la dernière 
        opération exécutée de cette fonction (ou encore : l'appel n'a pas d'enveloppe).
      
    </p>

<p>

      
        La récursion terminale est utilisée principalement dans les langages de programmation 
        fonctionnels pour exprimer un processus intératif dans une forme fonctionnelle récursive. 
        Les langages de programmation fonctionnels peuvent généralement détecter la récursion 
        terminale et optimiser l'exécution de façon à itérer, en économisant ainsi l'espace de la 
        pile d'appel, comme décrit ci-dessous.
      
    </p>

<p>

      
        Prenons ce programme Scheme comme exemple :
      
    </p>

<p>

      
           (define (factorielle n)
      
    <br/>

      
             (define (iterer n acc)
      
    <br/>

      
               (if (<= n 1)
      
    <br/>

      
                   acc
      
    <br/>

      
                   (iterer (- n 1) (* acc n))))
      
    <br/>

      
             (iterer n 1))
      
    </p>

<p>

      
        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 :
      
    </p>

<p>

      
           call factorielle (3)
      
    <br/>

      
            call iterer (3 1)
      
    <br/>

      
             call iterer (2 3)
      
    <br/>

      
              call iterer (1 6)
      
    <br/>

      
               call iterer (0 6)
      
    <br/>

      
               retourne 6
      
    <br/>

      
              retourne 6
      
    <br/>

      
             retourne 6
      
    <br/>

      
            retourne 6
      
    <br/>

      
           retourne 6
      
    </p>

<p>

      
        après réorganisation :
      
    </p>

<p>

      
          call factorielle (3)
      
    <br/>

      
           remplace les arguments avec (3 1), jump into "iterer"
      
    <br/>

      
           remplace les arguments avec (2 3), re-iterer
      
    <br/>

      
           remplace les arguments avec (1 6), re-iterer
      
    <br/>

      
           remplace les arguments avec (0 6), re-iterer
      
    <br/>

      
           retourne 6
      
    </p>

<p>

      
        (l'espace consommée est proportionnel à l'indentation)
      
    </p>

<p>

      
        Cette réorganisation économise de l'espace car aucun état, sauf l'adresse de la fonction 
        appelante, n'a besoin d'être sauvé sur la pile ou sur le tas. 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.
      
    </p>

<p>

      
        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. Dans certains cas (comme pour le 
        filtrage de listes) et dans certains langages, la récursion terminale nécessite de 
        réécrire une fonction dans un style non-fonctionnel : c'est-à-dire une fonction qui altère 
        le contenu de variables passées en argument par référence.
      
    </p>

<p>

      
        Pour finir, voici une version enveloppée de factorielle :
      
    </p>

<p>

      
          (define (factorielle n)
      
    <br/>

      
            (cond ((= n 0) 1)
      
    <br/>

      
                  (else (* n (factorielle (- n 1))))))
      
    </p>

<p>

      
        Le résultat de l'appel récursif (factorielle (- n 1)) est utilisé par la fonction *, qui 
        constitue ici l'enveloppe. A 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. 
      
    </p>