“Recursion is beautiful, but computers don't really grok beauty.”
-- Larry Wall

Unfortunately this is true of Perl. While Perl 6 still holds some hope for tail-recursion optimisation, there’s no way to get the performance and elegance in Perl 5.

Tail Recursion

Tail recursion is signified by the recursive call being last executed statement. It can match iterative algorithms for speed and space usage as there is no unwinding phase needed, so the same stack frame can be used repeatedly instead of pushing another one on each call.

In your above code (repeated below) you used straight recursion.

    # A classic, recursive soulution.
    sub Rfactorial {
        my $i = shift;
        return 1 if $i == 0;
        return 1 if $i == 1;
        return $i * Rfactorial($i - 1);
    }
[download]

Compare that to the same function rewritten in a tail recursive manner.

    # Tail recursive
    sub factorial {
        my $n = shift;
        return 0 unless $n > 0;
        fact( $n, 1 );
        
        sub fact {
            my($n, $a) = @_;
            return $a unless $n > 1;
            fact( $n-1, $n*$a );
        }
    }
[download]

With an optimising compiler the tail recursive version would be comparable to an iterative approach in performance, while retaining it’s (arguable) elegance. This particular example doesn't look much easier or more elegant, but it can be.

As stated above though, Perl doesn’t optimise any form of recursion. So the best bet is to write it in some iterative fashion if you want performance.

See Also

• “Tail Recursion” entry in Wikipedia

---

(1) I didn’t bother trying to keep the fact() sub local for reasons of claity