Tail Recursion

Consider the following 2 recursive functions

def gcd(a:Int,b:Int):Int ={
if(b==0)
b
else
gcd(b,a%b)


def factorial(n:Int):Int={
if(n==0)
1
else
n *factorial(n-1)


There is an important difference between the two rewrite sequences: The terms in the rewrite sequence of gcd have the same form repeatedly. As evaluation proceeds, their size is bounded by a constant.

By contrast, in the evaluation of factorial we get longer and longer chains of operands which are then multiplied in the last part of the evaluation sequence.

In the implementation of gcd, one notes that the recursive call to gcd is the last action performed in the evaluation of its body. One also says that gcd is tail-recursive.

The final call in a tail-recursive function can be implemented by a jump back to the
beginning of that function. The arguments of that call can overwrite the parameters
of the current instantiation of gcd, so that no new stack space is needed. Hence,
tail recursive functions are iterative processes, which can be executed in constant
space.
By contrast, the recursive call in factorial is followed by a multiplication. Hence,
a new stack frame is allocated for the recursive instance of factorial, and is deallocated
after that instance has finished. The given formulation of the factorial function
is not tail-recursive; it needs space proportional to its input parameter for its
execution.
More generally, if the last action of a function is a call to another (possibly the same)
function, only a single stack frame is needed for both functions. Such calls are called
tail calls. In principle, tail calls can always re-use the stack frame of the calling
function.