I understand that "a" solution is:
function Factorial(number)
{
if(number == 0 || number == 1){
return 1;
}
return number * Factorial(number -1);
}
I want to understand what exactly is going on. I understand what is going on all the way to the last part when number == 1.
If we were to take a simple example of say 3!
- 3 is not equal to 0 or 1 so we return 3 * Factorial(2)
- 2 is not equal to 0 or 1 so we return 2 * Factorial(1)
- 1 is equal to 1 so we return 1
How do we know when to stop? Is it the fact that we return 1 that tells the function to stop?
If that is the case, why does the function not stop when we first return 3 * Factorial(2)? Is it because it's returning a function so that it must continue until it no longer returns a function?
Thank you
I understand that "a" solution is:
function Factorial(number)
{
if(number == 0 || number == 1){
return 1;
}
return number * Factorial(number -1);
}
I want to understand what exactly is going on. I understand what is going on all the way to the last part when number == 1.
If we were to take a simple example of say 3!
- 3 is not equal to 0 or 1 so we return 3 * Factorial(2)
- 2 is not equal to 0 or 1 so we return 2 * Factorial(1)
- 1 is equal to 1 so we return 1
How do we know when to stop? Is it the fact that we return 1 that tells the function to stop?
If that is the case, why does the function not stop when we first return 3 * Factorial(2)? Is it because it's returning a function so that it must continue until it no longer returns a function?
Thank you
Share Improve this question edited Apr 9, 2015 at 17:39 1010 1,85819 silver badges28 bronze badges asked Apr 9, 2015 at 17:18 sjmartinsjmartin 3,9624 gold badges22 silver badges32 bronze badges 3- 1 "Is it because it's returning a function so that it must continue until it no longer returns a function?" <- Precisely – Rick Hitchcock Commented Apr 9, 2015 at 17:22
- 1 Do note that this function creates an infinite loop when not called with a positive whole number. – Rick Hitchcock Commented Apr 9, 2015 at 17:23
-
1
The last thing that happens is that 3 is multiplied by the value returned from
Factorial(2)
. That's the ultimate returned value. That step cannot happen untilFactorial(2)
is finished, andFactorial(2)
can't finish untilFactorial(1)
finishes. – Pointy Commented Apr 9, 2015 at 17:23
5 Answers
Reset to default 5I think you have to understand the logic of factorial.
So factorial is just products, indicated by an exclamation mark ie, if you write
0! = 1
1! = 1
2! = 2*1
3! = 3*2*1
4! = 4*3*2*1
5! = 5*4*3*2*1
Hope you find the pattern, so you can write the above factorials as:
0! = 1
1! = 1
2! = 2*1!
3! = 3*2!
4! = 4*3!
5! = 5*4!
So in your function you are using the similar logic.
Now in your function
if(number == 0 || number == 1)
{
return 1;
}
The above logic is to cover the first two cases i.e, 0! and 1! And
return number * Factorial(number -1);
is for the rest of the numbers.
So you are using the recursive technique of solving the factorial problem.
To understand recursion, lets take a number say 5 i.e., we want find the value of 5!.
Then first your function will check
if(number == 0 || number == 1)
which is not satisfied, then it moves to the next line ie,
return number * Factorial(number -1);
which gives
5*Factorial(5-1) which is equal to 5*Factorial(4)
Now on subsequent calls to your Factorial function it will return the value like below:
5*(4*Factorial(4-1)) which is equal to 5*(4*Factorial(3))
5*(4*(3*Factorial(3-1)) which is equal to 5*(4*(3*Factorial(2)))
5*(4*(3*(2*Factorial(2-1)))) which is equal to 5*(4*(3*(2*Factorial(1))))
Now when it returns factorial(1) then your condition
if(number == 0 || number == 1)
is satisfied and hence you get the result as:
5*4*3*2*1 = 120
On a side note:
Beware that factrial is used only for positive integers.
Recursion relies on what is called a base case:
if(number == 0 || number == 1){
return 1;
}
That if
statement is called your base case. The base case defines when the recursion should stop. Note how you are returning 1
not returning the result of a call to the function again such as Factorial(number -1)
If the conditions for your base case are not met (i.e. if number
is NOT 1 or 0) then you proceed to call the function again with number * Factorial(number - 1)
If that is the case, why does the function not stop when we first return 3 * Factorial(2)?
Your simple example of 3! can be elaborated like this :
return 3 * Factorial(2)
will then be replaced by
return 3 * (2 * Factorial(1))
which then will be replaced by
return 3 * (2 * 1) // = 6 Hence 6 is returned at last and recursion ends.
How do we know when to stop?
When all your Factorial(value) is replaced by a returned value we stop.
Is it the fact that we return 1 that tells the function to stop?
In a way, yes. Because it is the last returned value.
It is called recursion.
This function is called like this
var result = Factorial(3); in Factorial function
First time return 3*Factorial(2);
Now here return statement doesnt get executed insted Factorial is called again.. so second time return 2*Factorial(1);
again in Factorial(1) Third time return 1;
So go to second return 2*1;
Next to first return 3*(2*1);
Finally var result = 3*2*1 = 6.
The function is recursing (calling itself) - and taking one from "number" each time.
Eventually (as long as its a positive integer you call it with, otherwise you'll probably get an infinite loop) you'll always hit the condition (number == 1) so instead of recursing further, it'll return 1 rather than call the function again.
Then, once you have hit the bottom (1), it'll start to run the function and work back up the other way along the function call stack, using the previous result each time:
1 = 1
(2*1) = 2
(3*2) = 6
(4*6) = 24
etc
So the final return statement from the function will return the required result