Is perl tail recursive?
-----------------------
::
In article <4aopge$le2@sunti1.sdm.de>, Steffen Beyer wrote:
>I was wondering what on earth _IS_ tail recursion?!?! :-)
A function is said to be recursive if it (sometimes) calls itself,
whether directly or indirectly. For example, here is a recursive
definition of the factorial function.
sub factorial {
return 1 if $_[0] == 0;
$_[0] * factorial($_[0] - 1)
}
This definition requires O(n) space to evaluate: a new stack frame must
be allocated for each recursive call, so the space required to calculate
factorial(n) is proportional to n.
A (recursive) function is tail recursive if the value of the function is
the value of a recursive call to the function (with different arguments,
necessarily). In other words, a function is tail recursive if the last
thing it does is to call itself.
The factorial function can be made tail recursive by using an
accumulator argument, in which the final value is gradually built up.
sub iter_fact {
my($n, $a) = @_;
return $a if $n == 0;
iter_fact($n - 1, $n * $a)
}
sub trfact {
iter_fact($_[0], 1)
}
The point of rewriting it like this is that there's now an interesting
optimization that can be applied.
Because the value of a call to iter_fact (e.g. iter_fact(5, 1), which
evaluates to 120) is the same as the value of the recursive call (in
this case iter_fact(4, 5), also 120), there's no need to allocate a new
stack frame for the recursive call. Instead, it is possible simply to
copy the new actual parameters into the appropriate place, and jump to
the beginning of the function.
Continuing the example, the final call is iter_fact(0, 120). There's
only one stack frame for all six calls that have been made to
&iter_fact, so iter_fact(0, 120) returns directly to &trfact, which made
the original call.
With this optimization, trfact uses only O(1) (i.e. constant) space.
I would like to see perl implement tail recursion optimization.
Although it might seem very esoteric, there are some algorithms which
are most naturally expressed in a recursive style.
Furthermore, if all stack frames smell the same---I don't know if this
is true of perl---it's possible to use this optimization and save a
stack frame whenever the last thing a subroutine does is to call another
subroutine. (At least, I can't think of any reason why not. But it's a
long time since I did any compiler theory. :-)
sub r { return $_[1] if !$_[0]; r(substr($_[0], 0, length($_[0])-1),
$_[1] . substr($_[0], -1))} print r("\n,rekcah lreP rehtona tsuJ");
Tim.
Original headers::
From: tim@pipex.net (Tim Goodwin)
Newsgroups: comp.lang.perl.misc
Subject: Re: Is perl tail recursive?
Date: 14 Dec 1995 16:06:56 GMT
Organization: Unipalm PIPEX
Message-ID: <4api30$d7l@wave.news.pipex.net>
References:
<1995Dec13.203308.17464@netlabs.com> <4aopge$le2@sunti1.sdm.de>