Récursivité terminale

L'usage de la récursivité simplifie les écritures, mais elle a un coût en terme de performance. Cependant, il existe une forme de récursivité qui se traduit par une exécution itérative ne diminuant pas les performances. Cette forme de récursivité est très recherchée, car elle conserve l'élégance de l'écriture récursive tout en ne pénalisant pas les performances.

D'une manière simple, une récursivité entraînant une exécution itérative est reconnaissable lorsque le résultat de l'appel récursif est le résultat de la fonction.

Reconsidérons la définition de la factorielle. Est-ce une fonction à récursivité terminale ? Pour cela, considérons l'appel récursif (* n (factorielle (- n 1))). Nous constatons que le résultat de l'appel récursif (factorielle (- n 1)) n'est pas le résultat de la fonction car il est ensuite multiplié par n. La fonction factorielle ainsi définie n'est pas à récursivité terminale.

Considérons maintenant la fonction :

(define (pgcd a b)
 (cond ((> b a)   
        (pgcd b a))
       ((zero? b) 
        a)
       (else
        (pgcd b (modulo a b)))))

Cette fonction est-elle à récursivité terminale ? Pour cela, considérons les deux appels récursifs. Le résultat de ces appels est-il encore utilisé dans le corps de la fonction ou est-il directement retourné ? Comme dans les deux cas il est directement retourné, cette fonction est à récursivité terminale. Elle va donc être exécutée par le système Scheme de manière itérative comme si les appels internes à pgcd étaient traduits par des sauts inconditionnels (goto). Il en résulte un accroissement de performances.