### 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%       --

⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

Create A New User
Node Status?
node history
Node Type: note [id://400465]
help
Chatterbox?
 [choroba]: I've moved away from nvidia

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (13)
As of 2017-05-26 14:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favorite model of computation is ...

Results (190 votes). Check out past polls.