nothing to do after the function returns except return its value.
Since the current recursive instance is done executing at that point,
saving its stack frame is a waste. Specifically, creating a new stack
frame on top of the current, finished, frame is a waste. A compiler is
said to implement TailRecursion if it recognizes this case and
replaces the caller in place with the callee, so that instead of
nesting the stack deeper, the current stack frame is reused. This is
equivalent in effect to a "GoTo", and lets a programmer write
recursive definitions without worrying about space inefficiency (from
this cause) during execution. TailRecursion is then as efficient as
iteration normally is.
The term TailCallOptimization is sometimes used to describe the
generalization of this transformation to non-recursive TailCall?s. The
best-known example of a language that does this is the SchemeLanguage,
which is required to support ProperTailCalls. Recursion is the basic
iteration mechanism in Scheme.
Consider this recursive definition of the factorial function in C:
factorial(n) {
if (n == 0) return 1;
return n * factorial(n - 1);
}
This definition is not tail-recursive since the recursive call to
factorial is not the last thing in the function (its result has to be
multiplied by n). But watch this:
factorial1(n, accumulator) {
if (n == 0) return accumulator;
return factorial1(n - 1, n * accumulator);
}
factorial(n) {
return factorial1(n, 1);
}
The tail-recursion of factorial1 can be equivalently defined in terms of goto:
factorial1(n, accumulator) {
beginning:
if (n == 0) return accumulator;
else {
accumulator *= n;
n -= 1;
goto beginning;
}
}
From the goto version, we can derive a version that uses C's built-in
control structures:
factorial1(n, accumulator) {
while (n != 0) {
accumulator *= n;
n -= 1;
}
return accumulator;
}
And Perl
sub factorial {
my $arg;
$arg == 0 ? 1 : $arg * factorial($arg - 1);
}
