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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: