I’m currently making may way through a book called “Seven Languages in Seven Weeks” by Bruce A. Tate. So far it’s been an interesting read, but I’m far from finished.

One of the things in the book that caught my eye was a recursive factorial function in Haskell, which seemed so simple, that I had to see what it would look like in perl.

So I wrote up the following perl snippets to calculate factorials. There are, of course, multiple ways to do it as I’ll describe below. There are also (likely) many other ways which I haven’t thought of, so if you have an interesting solution, please share.

One of the things that really caught my attention was how simplistic the syntax was for writing somthing so complex. Recursion is a fairly simple idea once you’ve seen it in action – a function that executes itself. However, the implementation of recursion in a given programming language can be somewhat difficult to comprehend, especially for new programmers or those without programming experience.

Although I haven’t dived into Haskell quite yet, it seems to make implementing a factorial function so simple, that I kind of stumbled when trying to understand it, thinking I was missing something.. but it was all there in front of me!

Firstly, let’s clarify what a factorial is (from wikipedia):

In mathematics, the

factorialof a non-negative integern, denoted byn!, is the product of all positive integers less than or equal ton. For example,

So the factorial of 5 is 120. Or 5! = 120. Lets look at the Haskell example from the book.

let fact x = if x == 0 then 1 else fact (x - 1) * x |

The above line is saying “if x is 0, then the factorial is 1 – otherwise, call myself with (x – 1), multiplied by x”

Lets look at this in ghci (the Haskell console):

[jbl@watchtower tmp]$ ghci GHCi, version 7.0.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. Loading package ffi-1.0 ... linking ... done. Prelude> let fact x = if x == 0 then 1 else fact (x - 1) * x Prelude> fact 5 120 Prelude> |

After seeing how easy it was to implement the recursive factorial function in Haskell, here are my attempts in perl.

Firstly, using a loop:

#!/usr/bin/env perl use strict; use warnings; use feature "say"; my $nni = $ARGV[0] ? $ARGV[0] : 5; for my $i ( 1..($nni - 1) ) { $nni = $nni * $i; say $nni; } |

This first example doesn’t implement a function, and is really just bad (but still working) code. It requires that your base number be global and alterable, in this case $nni.

Now, lets try it with an actual function:

#!/usr/bin/env perl use strict; use warnings; use feature "say"; my $nni = $ARGV[0] ? $ARGV[0] : 5; sub fact { my ($nni) = @_; return !$nni ? 1 : fact( $nni - 1 ) * $nni; } say fact($nni); |

This second method works similarly to the Haskell implementation. It implements a function that calls itself, without any looping required.

However, it’s still not as concise as the Haskell version, so lets try again:

#!/usr/bin/env perl use strict; use warnings; use feature "say"; my $nni = $ARGV[0] ? $ARGV[0] : 5; my $fact; $fact = sub { my ($nni) = @_; !$nni ? 1 : $fact->( $nni - 1 ) * $nni }; say $fact->($nni); |

Aha, now we’re getting somewhere. In this third example, the fact() function is anonymous, and we’re assigning it to $fact via reference. This allows us to use $fact like an object with a single method that does the factorial calculation.

Although this is pretty much as concise as I was able to get it while taking readability into account, here’s a final example that goes a step further:

#!/usr/bin/env perl use strict; use warnings; use feature "say"; my ($nni, $fact); $nni = $ARGV[0] ? $ARGV[0] : 5; $fact = sub { !$_[0] ? 1 : $fact->( $_[0] - 1 ) * $_[0] }; say $fact->($nni); |

This last example uses perl’s pre-defined variable @_ which automatically holds a list of function arguments by default. I usually avoid doing this, since it hurts readability, especially for those who don’t live and breathe perl on a daily basis.

To my surprise, it would seem that Haskell has Perl beat (at least in this example) as far as readability + conciseness is concerned.

I haven’t spent much time playing golf here to reduce the number of lines or characters beyond the last example, but if anyone does come up with a tighter solution, please let me know!

**Edit** (20111005T22:43:50): Here’s a version I found that uses the Math::BigInt module

#!/usr/bin/env perl use strict; use warnings; use feature "say"; use Math::BigInt lib=>'GMP'; my $b = Math::BigInt->new($ARGV[0]); say $b->bfac(); |

This version is likely much faster, since the Math::BigInt package is intended to be used in situations where large integers are being handled.

Here’s the post I found with examples written in other languages as well: Factorial Challenge: Python, Perl, Ruby, and C