Factorial using Recursion in Java

Question

I am learning Java using the book Java: The Complete Reference. Currently I am working on the topic Recursion.

Please Note: There are similar questions on stackoverflow. I searched them but I didn't find the solution to my question. I am confused with the logic in the following program.

If I run the below program, it produces the correct output, but I didn't understand the logic.

• I didn't understand the logic in the following line : result = fact(n-1) * n;
• From my knowledge, If we pass the value of n=4 as shown in the below program,
• Then, 3 * 4 is stored in the result i.e., 12.
• Again, fact(n-1) is called. Then n becomes 3.
• Then the 2 * 3 is stored in the result replacing the previous 12.

• I think you understood where I am stuck up/confused.

• Thank you.

class Calculation
{
    int fact(int n)
    {
        int result;

       if(n==1)
         return 1;

       result = fact(n-1) * n;
       return result;
    }
}

public class Factorial
{
     public static void main(String args[])
     {
       Calculation obj_one = new Calculation();

       int a = obj_one.fact(4);
       System.out.println("The factorial of the number is : " + a);
     }
}

Answer 1

First you should understand how factorial works.

Lets take 4! as an example.

4! = 4 * 3 * 2 * 1 = 24

Let us simulate the code using the example above:

int fact(int n)
    {
        int result;
       if(n==0 || n==1)
         return 1;

       result = fact(n-1) * n;
       return result;
    }

In most programming language, we have what we call function stack. It is just like a deck of cards, where each card is placed above the other--and each card may be thought of as a function So, passing on method fact:

Stack level 1: fact(4) // n = 4 and is not equal to 1. So we call fact(n-1)*n

Stack level 2: fact(3)

Stack level 3: fact(2)

Stack level 4: fact(1) // now, n = 1. so we return 1 from this function.

returning values...

Stack level 3: 2 * fact(1) = 2 * 1 = 2

Stack level 2: 3 * fact(2) = 3 * 2 = 6

Stack level 1: 4 * fact(3) = 4 * 6 = 24

so we got 24.

Take note of these lines:

result = fact(n-1) * n;
           return result;

or simply:

return fact(n-1) * n;

This calls the function itself. Using 4 as an example,

In sequence according to function stacks..

return fact(3) * 4;
return fact(2) * 3 * 4
return fact(1) * 2 * 3 * 4

Substituting results...

return 1 * 2 * 3 * 4 = return 24

I hope you get the point.