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

How fitting that a discussion about recursion gets to over 12 levels of depth! ;-)

I must say that I'm surprised that the difference between recursion and iteration is as small as it is in this case. The problem I have had in some cases, though, is that perl starts to complain about deep recursion when I try recursive algorithms that go just one or two thousand levels down...