|
There is a special case of recursion where the cost of using recursion is much smaller than in the general case. Tail recursion is a situation where a recursive call is the last thing a function does before returning, and the function either returns the result of the recursive call or (for a procedure) returns no result. A compiler can recognize tail recursion and replace it by a more efficient implementation. (Generally, though, compilers only do that if you request that they optimize.)
For illustration, let's go back to the simple power function, without the improvement for even exponents. But this time, let's change how it works.
// powertimes(x, k, m) returns m*xk.
//
// Require: k > 0.
double powertimes(double x, int k, double m)
{
if(k == 1)
{
return m*x;
}
else
{
return powertimes(x, k-1, m*x);
}
}
The first case should be obvious. The second case uses the
fact that m*xk
= (m*x)*xk−1.
The definition of powertimes is tail-recursive. Notice that, after doing the recursive call, all it does is return the result produced by the recursive call. Since this is tail recursion, the recursive call can be replaced by (1) a change of the parameters, and (2) a jump back to the beginning of the function body. An optimizing compiler will replace it by the following.
double powertimes(double x, int k, double m)
{
start:
if(k == 1)
{
return m*x;
}
else
{
k = k-1;
m = m*x;
goto start;
}
}
That is expressed using a goto because that is how
the compiler actually works, but it can be written
just as well with a while-loop.
double powertimes(double x, int k, double m)
{
while(k != 1)
{
k = k-1;
m = m*x;
}
return m*x;
}
The point here is that these changes are done automatically
by the compiler. You can write the simpler recursive version.
What if you have a tail-recursive definition of powertimes, but you really want a definition of power? That is easy to manage.
double power(double x, int k)
{
return powertimes(x, k, 1);
}
That is, xk = 1*xk.
Be careful. Replacing a recursive call by a jump back to the start of the body only works when the call is tail-recursive. Our original definition of power,
double power(double x, int k)
{
if(k == 1)
{
return x;
}
else {
return x * power(x, k-1);
}
}
is not tail-recursive. After getting back from the
recursive call, it needs to multiply the result by
x.
What is the advantage of tail-recursion over general recursion? Answer
Is the following definition of g tail-recursive?
int g(int n)
{
if(n == 1)
{
return 2;
}
else
{
return g(n-1) + 3;
}
}
Answer
Write a definition of factorialTimes(n, m), which returns m*n!. Make the definition use tail recursion. Answer
|