Recursion in Java How does it work?

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

Answer 2

What you might be missing out here is that n is a variable local to your function. This means every call to your function (may it through recursion or not) gets a new variable n, which contains the parameter of that function. Because it is a value type, it is copied and not a reference to the original value. Therefore any changes to it in one call do not affect the variables in other (recursive) calls.

As a result your function first gets a copy of 6 and gives that reduced by 1 as a copy to the next call of your function. That call gets a "copy" of 6-1=5 and reduces it again - and so on. When it reaches 1 it also returns 1. Then it works its way up again through the call stack and multiplies the result of the last call with the local variable in this call. So 1 gets multiplied with 2 and gets returned. That result gets multiplied with 3 and so on. Finally you end up with the factorial.

Answer 3

In java, we have something called a stack.

Each time a method gets called by another method, it gets added to the stack.

 ________
|factR(1)| = <prints nothing>
 ________
|factR(2)| = 2
 ________
|factR(3)| = 6
 ________
|factR(4)| = 24
 ________
|factR(5)| = 120
 ________
|factR(6)| = 720

This basically means that for the factR(6) method to complete, factR(5) must complete, for factR(5) to complete, factR(4) must complete and so on.

In factR(6) you make a call to factR(5) and then wait for it to complete, because the result depends on it.

But, in factR(5), you too make a recursive call and you have to wait.

And so on, until we hit the limit factR(1), which will just return 1.

With factR(1) complete, factR(2) can then print out the result and return the result to its parent method, and so on, until factR(6) prints out and returns its results

Answer 4

The method should really be structured like this to find the factorial of n:

int factorial(int n)
{
    if (n == 1)
        return 1;

    return n * factorial(n - 1);
}

It isn't a very good idea, in my opinion to instantiate new variables inside of a recursive function because they'll simply be reset with each call because of scope.