Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things

Re: Pure Perl tail call optimization

by Limbic~Region (Chancellor)
on Mar 05, 2004 at 18:12 UTC ( #334306=note: print w/replies, xml ) Need Help??

in reply to Pure Perl tail call optimization

Eager to try my tail recursion, I tried your example and was bummed when it didn't work. I figured out that to make it work you had to do something like:
print tail_factorial(1, 8);
Where you had to supply an initial total for it to work. Here is a slightly modified version.
sub tail_factorial { my ($n, $total) = @_; $total = 1 if ! $total; return $total if ! $n; @_ = ($n - 1, $total * $n); goto &tail_factorial; }
To verify that it works I tested it for a value of 150 - no deep recursion errors - yeah. Thanks for the p6 weekly summaries too.

Cheers - L~R

Replies are listed 'Best First'.
Re: Re: Pure Perl tail call optimization
by demerphq (Chancellor) on Mar 09, 2004 at 19:48 UTC

    Your code is better written as

    sub loop_factorial { my ($n, $total) = @_; $total = 1 unless $total; while ($n) { ($n,$total) = ($n - 1, $total * $n); } return $total }

    Which is more efficient, and is IMO a better example of what a compiler that optimizes tail recursion would convert it to.


      First they ignore you, then they laugh at you, then they fight you, then you win.
      -- Gandhi

      Sure - but then it would not be recursive anymore. That is an iterative solution. I wanted to play with avoiding the deep recursion limit by using tail recursion. This is pdcawley's code, not mine.

      Cheers - L~R

        Note to other monks: This sub thread starting with my original reply to L~R is a little bit out of context. The subject of tail optimization came up in the CB and L~R's post was referenced (by L~R) and I replied to follow up on a paoint from the CB. Sorry about that if it appears out of place.

        I think the important thing to remember is the the whole hype around "tail recursion" and is really about "optimized tail recursion" is due to a fundamental equivelency between a tail recursive subroutine and its iterative equivelent. Its a very useful equivelency for language designers because it means that you don't need to supply any form of iterative control structures explicitly if you provide for automatic transparent optimization of tail recursive routines. But in languages with rich loop constructs like Perl there isnt much need to exploit it.

        In short whenever I hear people talking about how wonderful it is that they have found another weird way to emulate the normal tail recursion optimization in Perl I get a bit disdainful. The language comes with such a tool built in and reinventing it in kludgy ways like with goto is IMO not particularly impressive.

        Having said that its a pity Perl doesnt automatically optimize tail recursion, as it can involve a notational elegance that can be quite useful. My understanding is it should be a failry straightforward optimization so I wonder why it is that it hasnt happened. It could be just simply lack of tuits to do an optimization that isnt really needed I guess but it would be interesting to know if there are deeper issues.


          First they ignore you, then they laugh at you, then they fight you, then you win.
          -- Gandhi

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://334306]
[LanX]: ... and it might be your last chance ... I heard Perl is dead! OO
[marto]: someone read the post about search.cpan being shut down, and commented "It's going to be awhile before I learn to not type "" into my address bar."
[Discipulus]: ;=) the same here: S + ENTER is my way to cpan in browser

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (10)
As of 2018-06-20 09:40 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (116 votes). Check out past polls.