Explain recursion in factorial method

Question

I am new to computer science and learning recursion methods. Can someone explain this method briefly?

 import java.util.Scanner;

public class factorial {

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();

        System.out.print(factorial(n));

    }

    private static long factorial(int n) {      // HERE I DON'T UNDERSTAND HOW 
                                               //  THE MACHINE NOWS WHAT IS "factorial"
        if (n == 1)
            return 1;
        else
            return n * factorial(n - 1);               // ??
    }

}

Answer 1

def factorial(n):
    if n < 2:
        return 1
    else:
        return n * factorial(n-1)
factorial(4) # = 24
#You can replace code with your prefered language

Here is how it works

• If the value less than 2, it is actullay not returing mulitplication of two numbers, instead function returns multiplication of a number and a number return from a function call (n * factorial(n-1))
• At last we return 1

Example (Factorial of 4)

• Firstly it returns 4 * factorial (3)

• Then it returns 4 * 3 * factorial(2)

• Then it returns 4 * 3 * 2 * factorial(1). Here the else part of function ends

• Then at last it returns 4 * 3 * 2 * 1 = 24

Answer 2

we need to understand how call stack work to understand this.

Let me try explain as per your code :

1. System.out.print(factorial(n)); /*at this line ,lets assume n=3 ; as soon as we call factorial(3) , this method stores in Stack */

2. Above line will call method ; private static long factorial(int n) { ... } //n=3 i)it go inside and check if n==1 //false ii)its goes to else block : 3 * factorial(2) /* again here 3 * factorial(2) will store in stack on top of factorial(3) */ i)it checks again in if n==2 //false ii)goes to else : 2 * factorial(1) //stores on top of 3 * factorial(2) in stack i)it checks again in if n==1 // True , this returns value 1.

STACK looks like below in LIFO order:

2 * factorial(1)

3 * factorial(2)

factorial(3)

now question comes where this returned value 1 will go , It will go to top call from stack. which is ;2 * factorial(1)--> return 2 * 1

value 2 will go to stack of 3 * factorial(2) -- > which 3 * 2 =6

finally value 6 will go to called method : factorial(3).

Answer 3

Factorial of a number (n=number) is the product of all positive integers less than or equal to n. factorial of n can denote as n!
ex/
factorial of 5 = 5!
factorial of 100 =100!

 factorial of 5 means (5!) -> 5 * 4 * 3 * 2 * 1

ex/ according to this method

  1   private static long factorial(int n) {                                      
  2     if (n == 1){
  3       return 1;
  4     } else{
  5       return n * factorial(n - 1);
  6     }
  7   }

if we need to find 5! - (factorial of 5) you have to call the above method using number 5.
ex/

factorial(5)

if (n == 1) condition in line no:2 check the number you pass whether equal to 1 (because 1! is equal to 1) we use this line as our base case(where the place that recursive function stop)

base case
when we call recursion function it keeps calling again and again until our stack becomes overflow. therefore we need a "stopping point" to our recursive function. That endpoint we call as the base case

The main goal is to understand this line-

return n * factorial(n - 1);

in our first iteration n = 5 and n-1 = 4 (according to our example)

Imagine function calls like this

1st iteration 5! = 5 * factorial(4) - inside this line we keep 5 separately and * we call factorial(4) again

2nd iteration 4! = 4 * factorial(3) - inside this line we call factorial(3) again

3rd iteration 3! = 3 * factorial(2) - inside this line we call factorial(2) again

4th iteration 2! = 2 * factorial(1) - inside this line we call factorial(1) again

5th iteration 1! = 1 - start to return 1

Imagine return values like this

ex/
return 5 * factorial(4) -> 5 * [receive (4 * 3* 2* 1)] = 5 * (24)
factorial(4) - 4 * factorial(3) -> 4 * [receive (3 * 2 * 1) = 4 * (6)
factorial(3) -------> 3 * factorial(2) -> 3 * [recieve (2 * 1)] = 3 * (2)
factorial(2) --------------->2 * factorial(1) -> 2 * [return 1] = 1
this image will helpful (image I got from quora.com)
it keeps calling until our n equals to 1 once our function meets the base case which is n=1 it starts to return 1.

(keep in mind until it meets base case it keeps calling the function factorial(n) and until we meet our base case our function do not return anything)

Answer 4

The machine does not know what factorial is, the code there tells it how to calculate a factorial. It does this by saying "Is the number you gave me 1?" and until it is, returns the number times the function return of n - 1, essentially this will cascade into the calculation of a factorial.

This is easily seen if you take an example:

3! = 3*2*1

Or

3! = 3*2!

Which is what the return method gives in the form:

factorial(n) = n * factorial(n-1)

The program given:

factorial(3);

Will go through the following:

1. Is 3 equal to 1?
2. It is not so it returns 3*factorial(2)
3. In order to obtain 3*factorial(2), it calculates factorial(2).
4. Now it checks: is 2 equal to 1?
5. It is not so it returns 2*factorial(1), since it is returning to the step three, that overall return will now be 3*2*factorial(1).
6. Next the program checks: is 1 equal to 1?
7. It is so it returns 1.
8. This is returned to our call in step five: 2*factorial(1) becomes 2*1 = 2, which returns to the call from step 3, our first call, giving us 3*2 = 6, which is what the function will return overall.

This method could do with some tweaking though. Imagine you supplied it with 0? It would continuously call the factorial method on an infinite recursion because the sequence 0,-1,-2,-3,-4,... will never reach 1. A better method could look like this:

private static long factorial(int n) {

    if (n == 1 || n == 0) {
        return 1;
    } else if (n < 0) {  // factorials are not defined below 0, they can be interpolated
        return null;     // though, see note below
    } else {
        return n * factorial(n - 1);
    }
}

This function will now cover factorials for the whole range of integers, using a null solution for negative numbers. The definition for a factorial of n is defined as the product of the integers between 1 and n; see this. Factorials of negative integers, floating point numbers, and complex values are also defined or can be interpolated as noted in the link in the previous sentance, but these are much more complex than a simple recursive factorial.

Answer 5

It's all about breaking the problem into smaller versions of itself.

What is 1! ?

It's 1.

That's represented by the following code

    if (n == 1)
        return 1;

---

Can you find n! if you know (n-1)! ? Of course you can!

Just multiply it by n

represented by the other part of the code.

    else
        return n * factorial(n - 1); 

---

What you're doing is calling the function from within itself, eventually n will be 1, and the cycle will stop.

Answer 6

The rest of your code is irrelevant, lets break down your recursive function:

private static long factorial(int n) {     
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

What the first line, or signature, says, is "I am a private method (private) that is not attached to a specific object instance (static) that returns a long (which is a long integer value). I'm named 'factorial' because, presumably, the output is the factorial of the input. As input I take an int, which I'm naming n for my purposes.

We know factorials are defined as f(n) = n*(n-1)*...*1. Another way to write this is:

f(n) = n * f(n-1)

Or:

f(n) = n * (n-1) * f(n-2)
f(n) = n * (n-1) * (n-2) * f(n-3)

and so on. But when do you stop? when n == 1. We see this reflected in the method:

if (n == 1)
  return 1;//If n == 1, return 1. This is the 'base case'
else
  return n * factorial(n - 1);//Multiply n by the factorial of n-1 (duh, right?)

The recursive call here is in that last line: it's using the same function to figure out the solution to a problem that is smaller by a discrete amount. After all, we know that if we multiply n by the result of this smaller problem, we get the correct answer.

Answer 7

Your code:

private static long factorial(int n) {
    if (n == 1)
        return 1;
    else
        return n * factorial(n - 1);
}

defines a method named factorial. It could have been named func, fred, or anything you like; it would not change its behavior.

It's behavior is as follows:

• if the argument n is equal to 1, then it simply returns 1
• otherwise, it returns the product of n with the result of calling factorial with an argument equal to n - 1. This is the recursive step. Note that the function can call itself and it won't return until the recursive call returns. The chain of calls are pushed onto the stack, each one waiting for the next one to return before it computes the product and returns.

With a little thought, you should be able to see that the above behavior exactly matches a common textbook definition of the factorial function.

Assuming that factorial is called with an argument greater than 0, the recursion will always eventually end with a call to factorial with an argument equal to 1. As written, this function will fail with a stack overflow exception if it is called with a value of n that is less than 1.

Answer 8

Just take a sheet of paper and trace your code:

factorial(5):
5!=1:
    return 5*factorial(4):
    4!=1:
        return 4*factorial(3):
        3!=1:
            return 3*factorial(2):
            2!=1:
                return 2*factorial(1):
                1==1:
                return 1;

So, at the end we have: return 5*4*3*2*1 statement

Answer 9

It knows what factorial is because you defined it to be factorial.

You've created a private static long factorial(int n) which means "A method named factorial with a single parameter n that returns a long, is available statically on the factorial class, and is private to that class.

You can call factorial from anywhere that has access to it, which in this case is within the factorial class itself. This means you can call it from the main method, or you can call it from the factorial method itself. It's just a function call that, well, happens to call itself.

We know the definition of factorial, 1 * 2 * ... (n-1) * n. We can also define it as n! = n * (n - 1)! or in other words, factorial(n) = n * factorial(n-1) which is exactly what you see in the last line.