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!

1. 3 is not equal to 0 or 1 so we return 3 * Factorial(2)
2. 2 is not equal to 0 or 1 so we return 2 * Factorial(1)
3. 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!

1. 3 is not equal to 0 or 1 so we return 3 * Factorial(2)
2. 2 is not equal to 0 or 1 so we return 2 * Factorial(1)
3. 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

• javascript

• 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 until Factorial(2) is finished, and Factorial(2) can't finish until Factorial(1) finishes. – Pointy Commented Apr 9, 2015 at 17:23

5 Answers 5

I 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