Recursion in Java How does it work? [duplicate]

Question

Please explain the working of the recursion statement in the following code.

int factR(int n) {
    int result;

    if(n==1) return 1;

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

My understanding is that:

In the above statement the factR(n-1) method calls itself until the end. Suppose we want to get the factorial of 6, which will be sent to this method as an argument. It will be received as the parameter n, and the value of n will then be checked; if it is 1 then 1 will be returned. But if it is not 1, as in our case where it is 6, then the recursion statement will run.

Now the problem I face is that the first time n-1 becomes 5 and is multiplied by n, which holds the value 6, then it becomes 30. Now where will that 30 GO?

Then the method will call itself and this time n-1 becomes 4 and it then multiplies with n which IF holds the value "6" then 4*6=24 which I think is wrong. Because if we go through this way then in the next call the process will be something like, n-1 will become 3*n which IF holds the same value i.e. 6 then it will become 3*6= 18. Then next call occurs and n-1 becomes 2 if we multiply and suppose that n holds the value 6 then 2*6= 12, and at last call n-1= 1 * n = 6. My point is that it is clear that n-1 will decrease the value n-1 i.e. 6-1=5 then 5-1=4 then 4-1=3 then 3-1=2 and 2-1=1. BUT the question is what will be the value of n which will be multiplied each time when the method calls itself?

If you say that when the first multiplication happens i.e. "n-1" become 5 then multiplied by 6 = 30 and that 30 is stored at "n" then in the next call 5-1=4*30=120, then 4-1=3*120=360 , then 3-1=2*360=720, and at last 1*720=720 then how does Java determine to put the resulting value back into the variable n?

If I place another statement to check what is the value of variable result each time the method call itself in this way, like this:

int factR(int n) { 
    int result; 

    if(n==1) return 1; 

    result = factR(n-1)*n ;
    System.out.println(result);
    return result; 
}

Then I get this output:

2
6
24
120
720
Factorial of 6 is 720

I don't understand how it produces 2 in its first call. Where does the value 2 and then 6, 24, 120 and 720 come from? I think I am severely stuck in the working of the code.

Answer 1

The function expands until the termination statement is reached (n == 1). So suppose n = 6, then we have factR(n-1) * n = factR(5) * 6, but what is factR(5)? Well it is just factR(4) * 5, and so we see that factR(5) * 6 = (factR(4) * 5) * 6. Now note that factR(1) = 1, and we get

factR(6) = factR(5) * 6 
         = (factR(4) * 5) * 6 
         = ((factR(3) * 4) * 5) * 6 
         = (((factR(2) * 3) * 4) * 5) * 6 
         = ((((factR(1) * 2) * 3) * 4) * 5) * 6 
         = ((((1 * 2) * 3) * 4) * 5) * 6
         = (((2 * 3) * 4) * 5) * 6
         = ((6 * 4) * 5) * 6
         = (24 * 5) * 6
         = 120 * 6
         = 720