◅ split into word and the rest of string

GDBM_File barfs on NFS mounted disk ▻

# Is perl tail recursive?

In article <4aopge$le2@sunti1.sdm.de>, Steffen Beyer <sb@sdm.de> 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: <m2pwdx6d8o.fsf@lily.sirius.com> <1995Dec13.203308.17464@netlabs.com> <4aopge$le2@sunti1.sdm.de>