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;
}

[download]

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);

    [download]
    Maybe someone else can explain that.
    Caution: Contents may have been coded under pressure.
[reply]
[d/l]

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

      [download]

      Benchmark code:

      Read more... (746 Bytes)
[reply]
[d/l]
[select]

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

        [download]
        Read more... (2 kB)

        ⠤⠤ ⠙⠊⠕⠞⠁⠇⠑⠧⠊

[reply]
[d/l]
[select]

In Section Seekers of Perl Wisdom