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.