Tail recursion

In computer programming, tail recursion uses a tail call to perform a recursive function. A tail call is when a function is called as the last act of another function. For instance, in this JavaScript program:

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

Here, the call to myTailFunc(myVar) is a tail call because it is the last operation of myFunc(myVar). When the compiler sees that it is the final operation of myFunc, it can perform a small optimization. Essentially, it does not need to push a return address onto the stack, because it doesn't need to return to myFunc. It can return the return value of myTailFunc as the return value of myFunc.

This small optimization becomes more significant when used in a recursive function. Normally, each level of recursion would require an additional return address to be pushed onto the stack. Tail recursion makes this unnecessary.

Here is an example of a simple JavaScript factorial function written first without, and then with, tail recursion.

Factorial function without tail recursion

var factorial = function (n) { 
  if (n == 0) { 
    return 1; 
  } else { 
    return n * factorial (n - 1); 
  } 
};

This function is recursive, but not tail recursive. The final process of the function is the multiplication operation ("*"), so the recursion always needs to return to the calling function.

Factorial function with tail recursion

var factorial = function (n) { 
  var recursion = function (n, subTotal) { 
    if (n == 0) { 
      return subTotal; 
    } else { 
      return recursion(n - 1, n * subTotal); 
    } 
  }; 
  return recursion(n, 1); 
};

Function, Programming terms