Factorial using Ruby (App Academy Practice Problem)

Hi again. Here’s the next problem — find the factorial of a number.

Here are the instructions from App Academy:

# Write a method that takes an integer `n` in; it should return
# n*(n-1)*(n-2)*…*2*1. Assume n >= 0.
#
# As a special case, `factorial(0) == 1`.
#
# Difficulty: easy.

I’m going to show three ways to solve this problem — first using a ‘while’ loop, then with a more ‘Rubyish’ way using ‘inject’, then finally introducing the concept of recursion.

Before anything, let’s think of the pseudocode for solving this problem:

1. We are given a number — n
2. We will be multiplying n by something a number of times (n * n-1) etc, so we’ll somehow need to store this in a variable
3. We are going to need a loop, starting at 1, and ending at n
4. We have a ‘base case’ — factorial(0) = 1
5. We are assuming n >= 0 (this is important because without this assumption we would need another base case — (n <= 0 would return nil))

Here’s the code for the while loop answer:

def factorial(n)
 if n < 0
  return nil
 end
#if n == 0
#  return 1
#end
 result = 1
 while n > 0
  result = result * n
  n -= 1
 end
 return result
end

We start with a base case:

if n < 0
  return nil
 end

This is not actually necessary since the problem says we can assume that n>= 0, but it’s good to have anyway. Also, what this is saying, in plain English, is that there is no factorial if the number entered is less than 0, so we’re returning nil.

Next, we deal with the special case where factorial(0) = 1:

#if n == 0
#  return 1
#end

The ‘#’ mark means that the code has been commented out — which means that it wont run. Really, the code is just here for illustration because it’s not necessary (see the while loop below). What it’s saying is that, if n is equal to 0, we are returning 1. That is considered a ‘base case’ and we immediately return a value from the function without needing the loop.

We now set up a variable for keeping track of every time we multiply n*n-1, n*n-2…we’ll call this variable ‘result’. We need to set an initial value for ‘result’ when we declare the variable. Since we’ll be multiplying n*n-1 until we reach ‘1’, we set result’s initial value to be 1.

result = 1

We next set up the while loop:

while n > 0
  result = result * n
  n -= 1
end

In the first line, we initialize the while loop when n > 0. Referring to the above discussion of n == 0 as a base case, if n == 0, the while loop will not run (since the loop only runs while n > 0). Therefore, since result = 1, we skip the loop, and return result with the correct answer. That is why:

#if n == 0
#  return 1
#end

is not necessary.

If, however, n > 0 (say n == 4), the first time through the loop, the result will equal the value currently set for result (1) * n, which equals 4. We then decrease n by 1.

Here we introduce the magic of the ‘puts’ statement.

result = 1
 while n > 0
  result = result * n
  puts result
  n -= 1
end

The ‘puts’ statement is great for debugging and seeing your output as you run your code.

Here’s the test output in the console after the ‘puts’ statement:

Tests for #factorial
===============================================
factorial(0) == 1: true
1
factorial(1) == 1: true
2
2
factorial(2) == 2: true
3
6
6
factorial(3) == 6: true
4
12
24
24
factorial(4) == 24: true
===============================================

App academy has tests for these problems (which are all passing), but the more important part is how the ‘puts’ statement shows me the value of ‘result’ each time the loop is executed.

First — note that when factorial(0), meaning n is set to 0, there is no output from the ‘puts’ statement. This means that the ‘while’ loop has been skipped, as was mentioned above.

When n == 3, result is initially 1 outside of the loop, then result becomes 3 (where n =3*result =1), then result is 6 (3 * 2), then finally 6 again (6 * 1). At that point n == 1, result == 6, and result is returned from the function with the correct answer.

Using ‘puts’ statements are critical for figuring out solutions to these problems. If some part of your code isn’t working, a ‘puts’ statement could help figure out where the code is broken, and how to fix it. It’s definitely an art and a science to figuring out where to ‘puts’ statements should go, but with practice you get better at figuring out flow of control and how ‘puts’ statements can help debug code. Here’s an article for using print statements to debug python.

A more ‘Rubyish’ solution: Using ‘inject’:

def factorial(n)
 if n == 0 
  return 1 
 else 
  return (1..n).inject {|product, n| product * n }
 end 
end

Unlike above, here we do need the base case, n == 0.

if n == 0 
  return 1

Without this base case, our test would fail when n == 0.

Here’s some documentation on using inject. It’s mostly text, and most of it is totally incomprehensible to me (just being honest), so I’ll just look at the code example to see how it’s used.

# Sum some numbers
(5..10).reduce(:+)                             #=> 45
# Same using a block and inject
(5..10).inject { |sum, n| sum + n }            #=> 45
# Multiply some numbers
(5..10).reduce(1, :*)                          #=> 151200
# Same using a block
(5..10).inject(1) { |product, n| product * n } #=> 151200

OK I solved this using ‘inject’, but it looks like I also could have used ‘reduce’. Let’s try that.

This is probably a good time to mention ‘repl.it’. App Academy links to this site for its code challenges, and I also heard about it from a friend of mine. It’s a good online code editor, although using Sublime or an IDE are still probably better.

Here’s an answer using reduce:

def factorial(n)
  if n == 0 
   return 1 
  else 
   return (1..n).reduce(1, :*)
  end 
end

There’s a lot of magic happening with ‘inject’ and ‘reduce’, but if you understand the logic behind the ‘while’ loop then these methods are basically operating the same way. Essentially, in this one line, very Rubyish way, the loop is executed and you get your answer. There’s a lot more to know about Ruby ‘symbols’ and ‘blocks’, but as a beginner programmer so much of this seems like magic anyway. There’s a lot more time to dive into the details of how these methods work.

Finally, here’s a solution using recursion:

def factorial(n)
 if n == 0
  return 1
 else
  return n * factorial(n-1)
 end
end

Recursion is a confusing topic — so I’ll leave it to someone smarter than I to explain. Here’s a video from the wonderful people at Khan Academy explaining how this solution works (using Python). They also have a great video explaining how to find the fibonacci of a number using iterative and recursive methods. In general, Khan Academy has a number of extremely useful resources for learning programming, including their series on JavaScript which was created by none other than John Resig, creator of jQuery.

I’d also like to link to the excellent free (optional paid certificate) courses at edX for learning Python. I have found Python is a great language for learning programming basics, and the courses at edX are very beginner friendly and accessible.

I hope this has been helpful and I will keep posting my answers to these problems :)