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

Like this:

LikeLoading...

Related

This entry was posted on Monday, May 19th, 2008 at 1:47 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.