La récursivité est dite terminale si l'appel à la
fonction récursive ne fait pas appel à un traitement postérieur.
Utiliser la récursivité terminale permet généralement
d'avoir une plus grande efficacité car le compilateur pourra, au
lieu d'empiler les appels, procéder à une substitution.
Les méthodes length(), append(SList) et reverse()
sont implémentées de façon récursive terminale
grâce aux équations suivantes (la fonction rappend(l1,l2)
a pour effet de concaténer la liste inversée de l1
avec l2) :
-
length(l) = lengthAux(l, 0)
-
lengthAux(l, acc) = acc si l est vide, lengthAux(cdr(l),
acc + 1) sinon
-
rappend(l1, l2) = l2 si l1 est vide, rappend(cdr(l1),
cons(car(l1), l2)) sinon
-
append(l1, l2) = rappend(reverse(l1), l2)
-
reverse(l) = rappend(l, EMPTY)