Problems? Is your data what you think it is? 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; }

Replies are listed 'Best First'.
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 all is quiet...

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (4)
As of 2018-03-22 06:19 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (273 votes). Check out past polls.

Notices?