Hey, don't take me wrong, I'm all about elegance. My argument isn't against functional langauges (hell, I used reduce, which is the same thing in lisp! lisp, baby! how's that for functional!), it was that recursion in Perl is crazy inefficient, and to use it just because its "functional" is kind of silly. :) Tilly's point was about tail-recursion, which is an optimization that Perl doesn't support (for some reason, I honesetly don't have a clue why).

Tail recursion has a seldom-noted cost. Sure, it speeds up some recursive code. But it also means that if you get into trouble, a stack backtrace will be missing a lot of potentially useful context.

That said, you can manually do tail-recursion in Perl with goto. Unfortunately it is not as efficient as it should be, and I'm not entirely sure why.

That said, you can manually do tail-recursion in Perl with goto. Unfortunately it is not as efficient as it should be, and I'm not entirely sure why.

I think that it basically comes down to the fact that goto is just not all that efficient, and the amount of bookkeeping code needed to do that (for non-trivial implementations) outweighed the benefits.

-stvn

... it was that recursion in Perl is crazy inefficient, ...

Is it really? I mean, its certainly not as efficient as the equivalent iterative code. And I know that subroutine calls have a non-trivial overhead (setting up lexical scope and all), but being that perl does not tie itself to the C-stack like some other langauges do (*cough* Python *cough*) I would think that it wouldn't really be all that inefficient. Of course, I have never benchmarked it, so who knows.

... and to use it just because its "functional" is kind of silly ...

But if we can't get silly with Perl at 7 o'clock (EST) on a Friday night, then what kind of world is this! ;-P

about tail-recursion, which is an optimization that Perl doesn't support (for some reason, I honesetly don't have a clue why)

I don't know why either, I once looked into trying to "implement" it with the B:: modules. But once was all it took for me to to decide that wouldn't work.

-stvn

Well, here's a benchmark. The first two are just normal factorial functions. The second two are factorial functions with a twist: a simple string gets created. Now, this string has to be created and saved on *every* recursive call, which should show the discrepancy a little more (as saving one little integer to the stack doesn't make much difference):

use strict;
use warnings 'all';

sub factorial_r {
    my ($n) = @_;
    
    return $n if ($n < 2);
    return $n * factorial_r($n-1);
}

sub factorial_i {
    my ($n) = @_;
    
    my $i = $n - 1;
    $n *= ($n - $i--) while $i > 1;
    return $n;
}

sub factorial_r_extra {
    my ($n) = @_;
    my $x = "blah" x 100;
    return $n if ($n < 2);
    return $n * factorial_r_extra($n-1);
}

sub factorial_i_extra {
    my ($n) = @_;
    my $x = "blah" x 100;
    my $i = $n - 1;
    $n *= ($n - $i--) while $i > 1;
    return $n;
}

use Benchmark qw(timethese);
timethese(100000, {
    first  => sub { factorial_r(50) },
    second => sub { factorial_i(50) },
});
[download]

The results:

Benchmark: timing 100000 iterations of factorial_i, factorial_i_extra,
+ factorial_r, factorial_r_extra...
factorial_i:  5 wallclock secs ( 4.94 usr +  0.00 sys =  4.94 CPU) @ 2
+0251.11/s (n=100000)
factorial_i_extra:  6 wallclock secs ( 5.67 usr +  0.00 sys =  5.67 CP
+U) @ 17633.57/s (n=100000)
factorial_r:  6 wallclock secs ( 6.44 usr +  0.01 sys =  6.45 CPU) @ 1
+5496.67/s (n=100000)
factorial_r_extra: 13 wallclock secs (11.98 usr +  0.00 sys = 11.98 CP
+U) @ 8344.46/s (n=100000)
[download]

P.S. : I'm still young and armed with a job with flextime - I don't wake up until about 1pm, so this is like early afternoon for me. :)