“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

You can "optimise" out the stack frame in tail recursive code in perl5 using goto. E.g.:

sub fact {
    my($n, $a) = @_;
    return $a unless $n > 1;
    @_ = ($n-1, $n*$a);
    goto &fact;
}
[download]

However, this is so wildly slow it's rarely worth the effort :-)

If perl6 doesn't manage to do tail-recursion optimisation I hope we at least get an efficient way to throw away a call-stack level so we can code it by hand.

# caching previous answers 
use Memoize;
memoize('Mfactorial');
memoize('Mfactorial2');
sub Mfactorial {
    my $num = shift;
    return 1 if $num == 0 or $num == 1;
    return $num * Mfactorial($num - 1);
}
sub Mfactorial2 {
    my $iLex = shift;
    return 1 unless $iLex > 1;
    my $result =1;
    while ($iLex > 1) {
        $result = $result * $iLex;
        $iLex--;
    }
    $result;
}

__DATA__
results:
Benchmark: timing 1000000 iterations of Closure, Global, Lexical, Memo
+, Memo2...
   Closure: 25 wallclock secs (26.29 usr +  0.00 sys = 26.29 CPU) @ 38
+037.28/s (n=1000000)
    Global: 26 wallclock secs (26.41 usr +  0.00 sys = 26.41 CPU) @ 37
+864.45/s (n=1000000)
   Lexical: 28 wallclock secs (25.32 usr +  0.05 sys = 25.37 CPU) @ 39
+416.63/s (n=1000000)
      Memo: 16 wallclock secs (16.20 usr +  0.02 sys = 16.22 CPU) @ 61
+652.28/s (n=1000000)
     Memo2: 17 wallclock secs (16.13 usr +  0.03 sys = 16.16 CPU) @ 61
+881.19/s (n=1000000)
           Rate  Global Closure Lexical    Memo   Memo2
Global  37864/s      --     -0%     -4%    -39%    -39%
Closure 38037/s      0%      --     -3%    -38%    -39%
Lexical 39417/s      4%      4%      --    -36%    -36%
Memo    61652/s     63%     62%     56%      --     -0%
Memo2   61881/s     63%     63%     57%      0%      --
[download]

Recursion looks pretty good after this! Now, I don't know if your actual application would benefit from caching the results. We're looking at the classic recursive algorithm here, so YMMV.

If you want to duplicate this, be sure to call memoize before you benchmark.

$iClosure = shift;
[download]

our $iGlobal;
our $closure_sub = Cfactorial();
timethese (1000000,
{
'Recursion' => 'Rfactorial(30)',
'Global' => 'Gfactorial(30)',
'Lexical' => 'Lfactorial(30)',
'Closure' => '&{$closure_sub}(30)',
}
);
[download]

There is another standard algorithm that has a elegant recursive solution: mergesort. Your "benchmark" would be far more interesting with mergesort than with factorials. And make sure to test data sets of different sizes.

Abigail

To help you on your way, here's a recursive solution for merge sort:

    sub merge {
        my ($f, $s, @r) = @_;
        push @r => shift @{$$f [0] < $$s [0] ? $f : $s} while @$f && @
+$s;
       (@r, @$f, @$s);
    }
    sub merge_sort;
    sub merge_sort {
        @_ <= 1 ? @_ : merge [merge_sort @_ [0 .. @_ / 2 - 1]],
                             [merge_sort @_ [@_ / 2 .. $#_]]
    }
[download]

The recursive solution is elegant, and just 10 lines. I don't really want to think about the iterative solution.

Abigail

Is there any particular significance to your choice of $f, $s and @r as variable names? They don't seem to match up with the classic left, right and temp in either english or dutch?

---

..and remember there are a lot of things monks are supposed to be but lazy is not one of them

Examine what is said, not who speaks.
1) When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong.
2) The only way of discovering the limits of the possible is to venture a little way past them into the impossible
3) Any sufficiently advanced technology is indistinguishable from magic.
Arthur C. Clarke.

Recursion is slow because all the arguments must be pushed onto the stack (in the case of Perl, the @_ variable). By eliminating any arguments passed in a recursive algorithm, you eliminate the speed problem, since nothing needs to be pushed onto the stack.

The example above probably isn't the best example of this, since $iGlobal still needs to be shifted off the stack.

----
Reinvent a rounder wheel.

Note: All code is untested, unless otherwise stated

That only works if you don't have much state to remember. Recursion starts getting fun when there's significant state, for instance, when you are doing divide-and-conquer, a very common technique to solve problems. (Basically, it means: divide the data set into 2 or more smaller sets. Solve the problem for the smaller sets, then combine the answers). Sorting can be done that way (quicksort, mergesort), enumerating range queries on trees typically work this way, building convex hulls, etc, etc.

You can of course use iterative versions of the recursive algoritms. But you'll notice that for any non-trivial algorithm, you'll need a stack to remember your state.

Abigail

By eliminating any arguments passed in a recursive algorithm, you eliminate the speed problem, since nothing needs to be pushed onto the stack.

• That doesn't eliminate the recursion, it only eliminates the parameter passing.
• Only in trivial recursions can you eliminate the need to push variables on the stack.
• You still have to push the return address onto the stack, anyway.

SpaceAce
s>>sp>;s>..|>\u$&ace>g;print;