Thread: confused on this recursive method example

Try doing some debugging. Add some println statements to print out the values of variables as they are used. The printout will show you what the code is doing.

Recursion has two important parts:
1. An "exit case" - where a condition is reached such that no more recursive calls are made. In your example, k==1 is the exit case.
2. The recursive call - where the recursive method calls itself. In your example, mystery(k/2)

An important thing to note here is integer division. When you divide two integers in Java, any fractional remainder is ignored. So: 4/2=2, 5/2=2, 6/2=3, 7/2=3, ect.
The numbers are not rounded or anything. The decimals are just simply tossed away.

When you call a method in Java, the method does not finish until the method is exited (with a return statement, if a return value is required).
When you call: return (1 + mystery(k/2);, the method doesn't "finish" until the value of (1 + mystery(k/2)) is finished calculating. Since the method calls itself, the "instance" of the method which called mystery(k/2) has to wait until mystery(k/2) is finished evaluating.

So, you can imagine the recursive calculations unraveling like this:
int value = mystery(9);
int value = (1 + mystery(9/2)) ** 9/2 = 4
int value = (1 + (1 + mystery(4/2)) ) ** 4/2 = 2
int value = (1 + (1 + (1 + mystery(2/2)) ) ) ** 2/2 = 1
int value = (1 + (1 + (1 + (1 + (0)) ) ) )
int value = (1 + (1 + (1 + (1)) ) )
int value = (1 + (1 + (2) ) )
int value = (1 + (3) )
int value = 4