Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

Re^5: Behold! The power of recursion.

by audreyt (Hermit)
on Oct 19, 2004 at 10:57 UTC ( #400465=note: print w/ replies, xml ) Need Help??


in reply to Re^4: Behold! The power of recursion.
in thread Behold! The power of recursion.

Now one problem of course is that perl does not do this type of optimization :)
Sure, but you can tell it to do that. :-)
sub factorial { my ($n, $accumulator) = @_; $accumulator ||= 1; if ($n == 0) { return $accumulator; } @_ = ($n - 1, $n * $accumulator); goto &factorial; }


Comment on Re^5: Behold! The power of recursion.
Download Code
Re^6: Behold! The power of recursion.
by Roy Johnson (Monsignor) on Apr 08, 2005 at 21:39 UTC
    Ironically, the recursive form (just leave out "goto") is *much* faster. It's a little hard to tell using factorial, but you can see it in this:
    sub rec_max { return () unless @_; my ($h1, $h2) = (shift, shift); if (@_) { unshift @_, ($h1 > $h2) ? $h1 : $h2; &rec_max; # Try it with and without goto here } elsif (defined $h2) { return ($h1 > $h2) ? $h1 : $h2; } } use List::Util 'shuffle'; print rec_max shuffle(1..2000,1500..3000,3500..8000);
    Maybe someone else can explain that.

    Caution: Contents may have been coded under pressure.

      Indeed!

      Benchmark results:

      Rate uses_goto normal uses_amp uses_goto 94719/s -- -10% -14% normal 105040/s 11% -- -4% uses_amp 109823/s 16% 5% -- Rate uses_goto normal uses_amp uses_goto 94448/s -- -8% -14% normal 103141/s 9% -- -7% uses_amp 110408/s 17% 7% -- Rate uses_goto normal uses_amp uses_goto 94148/s -- -11% -14% normal 105616/s 12% -- -4% uses_amp 109985/s 17% 4% --

      Benchmark code:

        Manually optimize the tail call away yourself and get a very nice improvement in speed. I switched back to your node's parent's code because it was recursive and yours wasn't. I haven't decided where exactly recursion is so utterly losing

        Rate normal goto amp unrolled normal 7.91/s -- -75% -91% -95% goto 31.9/s 304% -- -63% -81% amp 85.5/s 981% 168% -- -50% unrolled 169/s 2044% 431% 98% --

        ⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://400465]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (9)
As of 2015-07-06 11:43 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (73 votes), past polls