Can someone explain how this recursive function produces 5 * 4 * 3 * 2 * 1 to get 120?
var factorial = function(n){
if (n === 0)
return 1;
else
return n * factorial(n - 1);
};
factorial(5); // spits out 120
If we use 5 like like in the example, once we got to the else statement wouldn't
return n * factorial(n - 1);
translate to 'return 5 multiplied by the factorial function(5-1); 5 times...
Am I wrong to feel this recursive function feels like a 'for loop?'
No, recursion and loops have a lot in common. In particular, it's very important that they both have a termination condition. :-) In this case, that termination condition is n === 0.
The best way to understand this is to single-step through the code in a debugger. Your browser has one, so you could put that code in a page and load it and walk through it.
To get you started:
You call factorial(5). Since n is not === 0, factorial calls itself with n - 1 (4)
Now we've recursed one level, and we're running factorial(4) (the call to factorial(5) still hasn't returned, it's waiting on us). Since n is not === 0, we call factorial(3) and wait for it to return.
...rinse, repeat until factorial(0) is called. Since n === 0 is true (at that point, there are five calls to factorial outstanding and stacked up), factorial(0) returns 1, and we can start unwinding the stacked up calls.
Now factorial(1) can finish by multiplying the result it got from factorial(0) by its copy of n (1) and returning that.
...which lets factorial(2) finish and multiply that by 2...
...rinse repeat...
Or to put it another way showing the nesting (recursion):
factorial(5)
return 5 * factorial(4)
return 4 * factorial(3)
return 3 * factorial(2)
return 2 * factorial(1)
return 1 * factorial(0)
return 1
And because you can't get enough diagrams (or at least I can't):
factorial(5) factorial(4) factorial(3) factorial(2) factorial(1) factorial(0)
calls ---------->
calls ---------->
calls ---------->
calls ---------->
calls ----------->
n is 0, so
returns 1
|
returns 1 * 1<-----------+
= 1
|
returns 2 * 1<------------+
= 2
|
returns 3 * 2<------------+
= 6
|
returns 4 * 6<------------+
= 24
|
returns 5 * 24<-----------+
= 120
Result: 120
Side note: That function doesn't allow for negative numbers; it could probably use a guard at the beginning...
The n changes:
5 * factorial(5-1) = 5 * 4 * factorial(4-1) = 5 * 4 * 3 * factorial(3-1) = 5 * 4 * 3 * 2 * factorial(1-1) = 5 * 4 * 3 * 2 * 1
Also to make this function better you could stop it when n is equal to 1, since the factorial of 1 is 1:
var factorial = function(n){
if (n === 1 || n === 0)
return 1;
else
return n * factorial(n - 1);
};
This function says: if you want to calculate factorial(5), well, that's really just
5 * factorial(4)
and if you want to calculate factorial(4), that's really just 4 * factorial(3)
5 * 4 * factorial(3)
and the thing about factorial(3) is that it's really just 3 * factorial(2)
5 * 4 * 3 * factorial(2)
and so on. But when you get down to factorial(0), the function finally stops (because of the if n == 0 case) and returns 1, without any further recursion. So you get
5 * 4 * 3 * 2 * 1
return n * factorial(n - 1) translates to (on the first run), "return (5 * 4!)". It doesn't do anything 5 times.
If we use 5 like like in the example, once we got to the else statement wouldn't
return n * factorial(n - 1);
translate to 'return 5 multiplied by the factorial function(5-1); 5 times...
No, it would translate to 'return n multiplied by the factorial function (n-1)' (5 times, because n starts at 5, decrements and enters the else clause until it reaches 0).
Repeat all of those steps until n is equal to 0. The if clause will then be true and the function will return 1.
So 1 is returned from factorial(0). Factorial(1) returns 1 * factorial(0), so 1 * 1 = 1.
Factorial(2) returns 2 * factorial(1), so 2 * 1 = 2.
Factorial(3) returns 3 * factorial(2), so 3 * 2 = 6.
Factorial(4) returns 4 * factorial(3), so 4 * 6 = 24.
Factorial(5) returns 5 * factorial(4), so 5 * 24 = 120.
