CODEWITHSUNDEEP
javascriptwordpressrecursionfactorial
jb07
jb07

Reputation: 81

Logic in factorial recursion call

I'm working to wrap my head around recursion and maybe I'm being too obsessive, but here goes:

In the javascript code 

var factorial = function(number) {
  // If the number is negative, it doesn't have a factorial. Return an
  // impossible value to indicate this.
  if (number < 0) {
    return -1;
  }

  // If the number is zero, its factorial is one.
  if (number === 0) {
    return 1;
  }

  // If the number is neither illegal nor zero, call factorial again,
  // this time passing in a smaller number. Eventually we'll reach 0,
  // causing each call to return to its caller and the recursion terminates.

  return number * factorial(number - 1);
};

factorial(5);

The recursive function returns 120 as expected, but why?

In drawing out the logic, 2 things trip me up: 1) Why is this even operable and 2) Though it is operable, why wouldn't it return -1?

1) Why is this even operable?:

In drawing this out and plugging 5 as an argument, in the return statement at the bottom, we get return 5 * factorial(5 - 1). Why does this equate to 20 as expected? Aren't we calling the function to return 5 * the value of factorial(5-1)? How can we multiply 5 by the value of something that hasn't even been determined yet? If this was simply 5 * (5-1) = 20, then that's obvious or even factorial(5) * (5-1) = 20 makes sense..

2)Though it is operable, why doesn't it return -1?:

As with the case above, eventually, we'll get to the point in the recursion where it'll look like 1 * factorial(1-1)... 1 * (1-1) = 0. And with this function plugging the number in to itself for operation, and with our base case saying "if the integer plugged in is zero, stop operation and return -1". Why isn't that happening here?

Apologies if this seems simple, I may be making it a bigger deal than in needs to be. I just want to learn :) .

Upvotes: 0

Views: 283

Answers (2)

mavili
mavili

Reputation: 3424

To add to winhowes' answer

How can we multiply 5 by the value of something that hasn't even been determined yet?

Well, we don't, not until we know the value of factorial(5-1). When factorial(5-1) is called, we don't actually do the multiplication yet, until we have a definite answer for that. So the 5 stays there and waits for the result of the function call to come back, but then the 4 also waits for factorial(4-1).. etc. Once the final call (i.e. factorial(1)) returns a definitive answer, it multiplies by whatever was waiting for it, and that in turn goes and multiplies with the previous waiting call.

So you have a top-down call of methods, and when you have the values, a bottom-up of multiplications occur. As illustrated in this diagram:

enter image description here

Upvotes: 2

winhowes
winhowes

Reputation: 8065

Great question - glad you're diving into recursion head on!

Let's walk through what's going on:

We start with factorial(5). This returns 5 * factorial(5-1) as you pointed out. In order to understand what factorial(5-1) is, we have to call the factorial function again.

factorial(5-1) returns 4 * factorial(4-1). Let's substitute that in to what we have above. That gives us 5 * 4 * factorial(4-1). Again we do factorial(4-1) and substitute that in. Which gives us 5 * 4 * 3 * factorial(3-1).

If we continue we get 5 * 4 * 3 * 2 * factorial(2-1) and then 5 * 4 * 3 * 2 * 1 * factorial(1-1).

Now something different happens here. factorial(1-1) returns 1 per the if condition:

// If the number is zero, its factorial is one.
if (number === 0) {
    return 1;
}

So we have 5 * 4 * 3 * 2 * 1 * 1 which = 120 = 5! as we expect. We're never going to hit the number == -1 if condition unless we put in a negative number. For any positive number, the number == 0 condition will catch every time.

Upvotes: 2

Related Questions