###
» 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).

## 4 Comments:

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

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

Actually, here is a more terse ruby version:

def fac(n) (1..n).reduce(1, :*) end

March 20, 2010 at 2:47 AM

@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

<< Home