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