Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
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 scrutinizing the Monastery: (5)
As of 2014-08-31 04:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (294 votes), past polls