CODEWITHSUNDEEP
rubyfactorial
hummmingbear
hummmingbear

Reputation: 2384

How is this method solving my factorial?

I'm working on a ruby challenge and had to write a method that would calculate the Factorial of a number. I came across a solution below, but I don't understand how it works, specifically the section in the else statement:

def factorial(number)
  if number <= 1
    1
  else
    number * factorial(number - 1)
  end
end

Lets say I run factorial(5) How is the else statement iterating through 5*4*3*2*1 in the number * factorial(number - 1) statement? I know this probably seems like it should be obvious, but it's not for me. Appreciate the help in advance.

Upvotes: 2

Views: 122

Answers (2)

Mark Reed
Mark Reed

Reputation: 95315

When you call factorial from the else, that's an example of recursion: calling the function you're currently in from itself. Which sounds weird, but what you're really doing is calling a new copy of the function, with a new argument. Which means that the flow starts over again from the top of the function, while remembering where to go back to when it finishes the new copy:

So you first call factorial(5), which does this:

def factorial(5)
  if 5 <= 1
    1
  else
    5 * factorial(5 - 1)

Well, now before we can continue we have to call factorial(5-1) and use its return value to replace that expression. Of course, Ruby does the subtraction before the call so by the time we get to the recursive call the argument is already just 4:

  def factorial(4)
    if 4 <= 1
      1
    else
      4 * factorial(4 - 1)

Whups, another recursive call. Here we go again:

    def factorial(3)
      if 3 <= 1
        1
      else
        3 * factorial(3 - 1)

And again:

      def factorial(2)
        if 2 <= 1
          1
        else
          2 * factorial(2 - 1)

And one more time:

        def factorial(1)
          if 1 <= 1
            1

Hold your horses! 1 is in fact less than or equal to 1, so we don't hit the else clause this time. We just return 1 to our caller up there in the factorial(2) copy - so where it had 2 * factorial(1), we replace factorial(1) with the return value, which is just 1:

          2 * 1
        end
      end

So that now returns 2 to its caller, which was the factorial(3) copy. That means that 3 * factorial(2) becomes just 3 * 2:

        3 * 2
      end
    end

And up in the factorial(4) copy, 4 * factorial(3) becomes 4 * 6:

      4 * 6
    end
  end

And finally, back up top in our original factorial(5) call, that 5 * factorial(4) becomes `5 * 24:

    5 * 24
  end
end

And that is of course the desired answer 120.

Upvotes: 1

hjing
hjing

Reputation: 4982

This concept is known as recursion.

factorial(5) evaluates to

5 * factorial(4)

factorial(4) evaluates to

4 * factorial(3)

factorial(3) evaluates to

3 * factorial(2)

factorial(2) evaluates to

2 * factorial(1)

factorial(1) evaluates to 1 because 1 <= 1

Substituting values appropriately results in

5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1

Upvotes: 5

Related Questions