r/learnjava • u/Apostle_1882 • Feb 08 '21
Help me understand recursion, please!
public static long method(long a, long b) {
if (b == 0) {
return b;
}
return a + method(a, b - 1);
}So this apparently resolves to essentially a * b. I really don't understand this. The base case only ever returns b when b is zero, so in my flawed logic it's always a * 0 = 0.
51
Upvotes
4
u/MatthiasDunkel Feb 08 '21
Ok, let me try to explain this. Let's assume
a = 3
b = 2
So the result should be 6. The idea of this code is to implement multiplication with addition (btw it is implemented like this in some architectures). So you would need to add 3 to itself self 2 times or b times. Let's simulate the code now.
The method gets a and b.
Step 1:
Check if b == 0. If not it returns 3 + method( 3, 1)
Note, that we are adding the returned value of the method to a. No multiplication involved. That is the recursion. We call the method in itself with new arguments:
So Step 2:
1 (b) is not 0 so we again return 3 + method(3, 0)
Step 3:
0 is equal to 0, so we return 0. In this case the new b.
So we return 0 to Step 2, where the method is waiting for the result:
3 + 0 = 3
This result is now returned to Step 1:
3 + 3 = 6
and this result is returned to the caller of the method. Think about the returns statements what they actually do. Hope I helped!