Recursion in Java How does it work?

Question

Please explain the operation of the recursive statement in the following code.

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

I understand that:

In the above statement, the factR(n-1) method calls itself to the end. Suppose we want to get a factorial of 6, which will be sent to this method as an argument. It will be accepted as parameter n , and then the value of n will 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 instruction will be executed.

Now the problem I am facing is that the first time n-1 becomes 5 and multiplies by n, which has a value of 6, then it becomes 30. Now, where will 30 GO be?

Then the method will call itself, and this time n-1 becomes 4, and then multiplied by n , which IF has the value "6", and then 4 * 6 = 24, which I think is incorrect. Because if we go this way, then in the next call the process will be something like: n-1 will become 3 * n, which IF has the same value, that is 6, then it will become 3 * 6 = 18. Then the following will happen call, and n-1 will become 2, if we multiply and assume that n has the value 6, then 2 * 6 = 12 and finally the call n-1 = 1 * n = 6. My point is that it is clear that n-1 will decrease the value of 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 every time, when does the method call itself?

If you say that when the first multiplication will occur, i.e. "n-1" becomes 5, then it is multiplied by 6 = 30 and that 30 is stored in "n", and then in the next call 5-1 = 4 * 30 = 120, then 4-1 = 3 * 120 = 360, then 3-1 = 2 * 360 = 720 and finally 1 * 720 = 720, then how does Java determine to return the resulting value back to the variable n ?

If I put another statement to check what the value of the result variable is every time the method calls itself this way, for example:

 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 do not understand how he produces 2 in his first call. Where did the value 2 come from, and then 6, 24, 120, and 720? I think I am very stuck in the code.

Answer 1

The function expands until an agreement on completion 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's just factR(4) * 5 , and so we see that factR(5) * 6 = (factR(4) * 5) * 6 . We now note that factR(1) = 1 , and we obtain

 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 may be missing here is that n is a variable local to your function. This means that every call to your function (whether it is through recursion or not) receives a new variable n , which contains the parameter of this function. Since this is a value type, it is copied and does not refer to the original value. Therefore, any changes in it in one call do not affect the variables in other (recursive) calls.

As a result, your function first obtains a copy of 6 and gives a decrease of 1 as a copy of the next call to your function. This 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 starts again through the call stack and multiplies the result of the last call with a local variable in that call. Therefore, 1 is multiplied by 2 and returned. This result is multiplied by 3 and so on. Finally, you get the factorial.

Answer 3

In java, we have something called a stack .

Each time a method is called by another method, it is 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 to complete factR(6) the factR(5) factR(6) method must end, to complete factR(5) execute factR(4) , etc.

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

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

And so on, until we reach the limit of factR(1) , which simply returns 1.

Upon completion of factR(1) factR(2) can print the result and return the result to its parent method, and so on, until factR(6) prints and returns the results

Answer 4

The method must be really structured in such a way as to find the factorial n :

 int factorial(int n) { if (n == 1) return 1; return n * factorial(n - 1); } 

It is not a good idea, in my opinion, to create new variables inside a recursive function, because they will simply reset with each call due to scope.