En programmation informatique, la récursion de la fin consiste à utiliser un appel de la fin pour effectuer une fonction récursive. Un appel de queue se produit lorsqu'une fonction est appelée comme dernier acte d'une autre fonction. Par exemple, dans ce programme JavaScript:

 var myTailFunc = function (myVar) {return myVar; }; var myFunc = function (myVar) {return myTailFunc (myVar); }; 

Ici, l'appel à myTailFunc (myVar) est un appel final, car il s'agit de la dernière opération de myFunc (myVar) . Lorsque le compilateur voit qu'il s'agit de l'opération finale de myFunc, il peut effectuer une petite optimisation. Essentiellement, il n’est pas nécessaire de placer une adresse de retour dans la pile, car il n’est pas nécessaire de retourner à myFunc . Il peut renvoyer la valeur de retour de myTailFunc en tant que valeur de retour de myFunc .

Cette petite optimisation devient plus significative lorsqu'elle est utilisée dans une fonction récursive. Normalement, chaque niveau de récursivité nécessite l’ajout d’une adresse de retour supplémentaire à la pile. La récursion de la queue rend cela inutile.

Voici un exemple de fonction factorielle JavaScript simple écrite en premier sans, puis avec, la récursion de la queue.

Fonction factorielle sans récursion de la queue

 var factorielle = fonction (n) {si (n == 0) {retour 1; } else {return n * factorial (n - 1); }}; 

Cette fonction est récursive, mais pas récursive. Le processus final de la fonction est l'opération de multiplication (" * "), de sorte que la récursivité devra toujours revenir à la fonction appelante.

Fonction factorielle avec récursion de la queue

 var factorial = function (n) {var récursivité = function (n, sous-total) {if (n == 0) {return subTotal; } else {return récursivité (n - 1, n * sous-total); }}; récursion de retour (n, 1); }; 

Fonction, Termes de programmation