in reply to Recursion Alternatives?

I'd say you picked a bad example. Factorial is a tail recursive function, which performs relatively badly. Calculating factorials with recursion is a nice example to introduce recursive programming. But an interative solution is well known to be much faster, without significant more code. (Your "global" and "lexical" solution are almost identical, which I call "iterative". Your closure solution doesn't make use a closure, all it does is return a code reference to an iterative solution).

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

Replies are listed 'Best First'.
Re: Recursion Alternatives?
by Abigail-II (Bishop) on Feb 27, 2003 at 10:14 UTC
    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

[reply]
[d/l]

      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.
[reply]
        first, second, result.

        Abigail

[reply]

In Section Meditations