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.

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. :)

I am not sure what you are trying to prove with this benchmark. Of course factorial_r_extra will take longer, it creates my $x = "blah" x 100 5,000,000 times, as opposed to factorial_i_extra which only creates it 100,000 times. That proves nothing about the inefficiency of recursion in perl, only that it takes longer to do something 50 times more, which is true regardless of whether you use iteration or recursion.

-stvn