Calculating Factorials in Ruby

20 Jan 2013

The factorial of a number is itself multiplied by itself-1 multiplied by itself-2, etc. all the way down until you multiply it by 1. By then it’s a giant number. In mathematics the denotation for this would be n! or, if n were 12, 12!.

But there’s no way in Ruby to make this mathy syntax work:

  12!  # that's "twelve factorial"

This is because the ! operator (pronounced “bang operator”) is picked up by the parser and merely negates the next term. If you type the above into IRB you’ll find that your REPL hangs because it’s waiting for more input.

One way to calculate a factorial in Ruby is the following

total = 1
12.downto(1) { |n| total *= n }

That’ll give you the correct answer (479,001,600). But… gross. There’s a local variable defined outside the block unnecessarily. A cleaner way would be:

12.downto(1).reduce(:*)

That gives the same answer. Let’s unpack that a bit. The 12.downto(1) would normally be something you’d give a block to, like in the first example. But in this case we’re not passing a block, we’re calling .reduce on the return value of .downto.

This works because downto returns an Enumerator instance. This is something that you can perform virtually any Enumerable method on. In this case we’ll call reduce.

If you’re not familiar with reduce, it’s the latter half of the famous “map/reduce” pair. A reduce function is given to each element in a list in turn and keeps track of the result from the previous time it was run. It might be a little clearer to see an example:

reduce = lambda {|last_result, element|  # Here we're creating a lambda (think "function")
  last_result = last_result + element    # that is named reduce that takes a thing and
}                                        # a new thing and adds them.

elements = [1,2,3]                       # Here's a collection that we can reduce.

                                         # We start with an initial value. This is because
                                         # the reduce function's first argument is the result
result = 0                               # of the previous call and to begin with 
                                         # that value needs to be created by hand.

elements.each {|element|                 # Now we call the reduce function we created
  result = reduce.call(result, element)  # once for each element.  Importantly: we remember
}                                        # the result each time and feed it back in
                                         # When we're done the `result` has the value we want
result ## => 6

This is a useful pattern because it allows us to separate our data from the functions we perform on it. Check out how easy it is to make the above code work on a list of strings instead of numbers:

elements = ["fee", "fi", "fo"]          # Strings also respond to the '+' method

result = ""                             # We have to initialize the result differently
                                        # now that we are using strings.

elements.each {|element|                # Everything else is the same!
  result = reduce.call(result, element)
}

result ## => "feefifo"

There are still a couple clunky bits here, however. We have to initialize the result each time and we are doing a fair bit of plumbing still. Luckily, all good reduce methods smooth out these rough edges. Here’s the API to the reduce method as implemented in Ruby’s Enumerable module:

(5..10).reduce(:+)  #=> 45                    # Sum some numbers
(5..10).inject {|sum, n| sum + n }            # Same using a block and inject
(5..10).reduce(1, :*)                         # Multiply some numbers
(5..10).inject(1) {|t, n| t*n }               # Same using a block
%w{ cat sheep bear }.inject do |memo,word|    # find the longest word
   memo.length > word.length ? memo : word
end  ##=> "sheep"

The reduce method is aliased to inject in Ruby so you may have already used it in your own code.

So the reason this factorial snippet works is that reduce is smart enough to take the first value from the list if you didn’t give it an initial value. It’s also smart enough to infer if you give it a proc object (which is what :* is here — (:*).to_proc == {|a,b| a * b })


Please if you found this post helpful or have questions.