Thursday, August 03, 2006

» Non-Recursive Factorial +

A common way to find a factorial in Ruby is to use a recursive function similar to this:

def fac(n)
if (n > 1)
n * fac(n - 1)
else
1
end
end

This is just the ruby implementation of the recursive Y-combinator for finding a factorial. Nothing wrong with that--if you live in a theoretical world of limitless stack space! But what if you want to calculate (why would you, I wonder?) the factorial of 926 or 1024 on your finite computer? Well, that's going to be a problem. On my machine, at about 860 levels of recursion into the #fac method ruby explodes with the error message: stack level too deep (SystemStackError). Doh.

But we can fix that quite easily. Instead of recursion (which involves allocating a new stack frame for every re-entry), we want iteration (which uses a single stack frame for every pass then discards it).

def fac(n)
sum = 1
sum.upto(n) { |i| sum *= i }
sum
end

Using the Fixnum#downto iterator method (Range#each would also work here, i.e., (1..n).each) we are able to calculate the factorial using a single stack that is discarded with each iteration--no more problem with running out of stack. And notice how elegantly this can be done in ruby; no gangly for or while loops, just a simple iterator and a block.

So what about speed? Both versions are pretty much equal. By cutting out the explicit comparison with 1, the explicit subtraction of 1 from n and the symbol table lookup for re-entry, we save a few clock-cycles; but not enough to make a big difference (around 30 milliseconds difference to find the factorial of 900).

Please note that I didn't invent this method of calculating factorials by iteration rather than recursion--it has been known for many years; I just thought it might prove useful to point out the difference between the two approaches in case anyone is not familiar, since the difference applies to other similar problems as well (e.g., file-system recursion).

5 Comments:

Blogger bruno said...

Late comment: here's a Python functional version:

from operator import mul
fac = lambda n: reduce(mul, xrange(n+1), 1)

In Python 2.5, it happens to be more than 2 times faster than the recursive version for !900
April 17, 2008 at 3:51 PM

 
Blogger MonkeeSage said...

Nice :)
June 25, 2008 at 2:23 PM

 
Blogger MonkeeSage said...

Ps. In ruby the functional version would look something like this:

fac = lambda {
    |n|
    Range.new(1, n).inject(1) {
        |x, y|
        x *= y
    }
}

It's about twice as slow as the iterator version.
April 18, 2009 at 5:58 AM

 
Blogger MonkeeSage said...

Actually, here is a more terse ruby version:

def fac(n) (1..n).reduce(1, :*) end
March 20, 2010 at 2:47 AM

 
Blogger Ezekiel said...

@bruno here's a tiny fix to the xrange part to get the result to be non-zero! :)

from operator import mul
fac = lambda n: reduce(mul, xrange(1, n+1), 1)
December 19, 2010 at 8:58 PM

 

Post a Comment

Links to this post:

Create a Link

<< Home