How would you write factorial?

ambs on 2008-09-22T20:16:17

There are a lot of ways to write a factorial function in Perl, from the more recursive functional approach, to the standard iterative solution.

I prepared a bunch (well, four for now). If you have any other creative way of coding this function, please let me know (by email or commenting here). Note that I am more interested in the algorithm than in the golfing or obsfuscation.

Solution 1: Recursive is beautiful

sub factorial {
	my $v = shift;
	if ($v > 1) {
		return $v * factorial($v-1);
	} else {
		return $v;
	}
}

Solution 2: Iterative is fast

sub factorial {
	my $v = shift;
	my $res = 1;
	while ($v > 1) {
		$res *= $v;
		$v--;
	}
	return $res;
}

Solution 3: Perl is a dynamic language

sub factorial {
	my $v = shift;
	return eval (join "*", (1..$v));
}

Solution 4: There are other ways of iteration

sub factorial {
	my $v = shift;
	my $res = 1;
	grep {$res*=$_} (1..$v);
	return $res;
}

---

Memoize and bignum

brian_d_foy on 2008-09-22T20:35:34

In my Mastering Perl class, I also show Memoize for the recursive solution, and bignum for all the solutions.

So, are you working on this as an article for TPR? :)

Re:Memoize and bignum

ambs on 2008-09-22T20:41:28

Just for fun (after reading http://www.willamette.edu/user/fruehr/haskell/evolution.html). But if people give me enough feedback, I think I'll write it :)

shouldn't this be optional

link on 2008-09-22T21:32:36

How about

sub fact
{
        my ( $n ) = @_;

        my @s = ();
        $s[0] = 1;

        foreach my $m ( 1 .. $n )
        {
                $s[$m] = 0;
                for( my $k = $m;$k>=1;$k--)
                {
                        foreach my $i ( 1 .. $k )
                        {
                                $s[$i] += $s[$i-1];
                        }
                }
        }
        return $s[$n];
}

Loads more available at http://www.luschny.de/math/factorial/FastFactorialFunctions.htm

re: How would you write factorial?

dug on 2008-09-22T21:56:25

Note that I am more interested in the algorithm than in the golfing or obsfuscation.

I wouldn't call this golfing or obfuscation. It's another take on the classic recursive algorithm, and might not be interesting. Anyway, here's how I'd write the recursive version:


sub factorial {
    my $v = shift;
    return 1 if $v == 1;
    return $v * factorial( $v - 1 );
}


I like to get the terminating case out of the way early on, and then read the meat of the algorithm (or soy of the algorithm, if you're inclined that way) afterward. I suspect I might be standing alone when I say that I find my version more readable for eliminating the if/then blocks, though.

I really liked your dynamic version of the algorithm, it's like the substitution model on steroids!

Cheers,

-- Douglas

reduce

bart on 2008-09-23T01:25:18

use List::Util qw(reduce);
sub factorial {
    my $v = shift;
    return reduce { $a * $b } 1 .. $v;
}

Too bad it produces spurious warnings:

Name "main::a" used only once: possible typo at test.pl line 5.
Name "main::b" used only once: possible typo at test.pl line 5.

Iterative, but not C-ish, but straightforward

Aristotle on 2008-09-23T03:00:00

sub factorial {
    my $f = 1;
    $f *= $_ for 2 .. shift;
    $f;
}

Re:Iterative, but not C-ish, but straightforward

Shlomi Fish on 2008-09-23T16:13:24

I would write it in a similar way too.