Could someone explain how this recursive code to reverse an int in java works please ?

Question

private static int reverse(int n, int r) {
  if (n == 0) return r;
  return reverse(n/10, 10*r+n%10);
}
public static int reverse(int n) {
 return reverse(n, 0);
}

I've tested this and it works, I just cannot figure out how. I know that the number is divided by ten and then goes into the loop again, but it seem as if until n becomes a decimal < 1, r isn't used at all. Help ?

Answer 1

r starts at 0 and at each recursive invocation the new value of r is set to 10*r+n%10. In a loop the equivalent would be r = 10*r+n%10.

When n is 0 the final value of r (which will hold the final result) is returned.

Here's how you can translate the code into a loop:

if (n == 0) return r;

If n is 0, no further recursion takes place. Since the function is tail-recursive (i.e. the result of each recursive result is simply returned), this means that the loop ends here. So our loop looks like this:

while(n != 0) {
}

So what happens if n is not 0:

return reverse(n/10, 10*r+n%10);

Ok, so the loop continues, with n/10 as the new value of n and 10*r+n%10 as the new value for r. So this is the loop we get:

while(n != 0) {
  n = n / 10;
  r = 10*r+n%10;
}

Answer 2

r IS used in the invocation to calculate a NEW number which is r shifted left one digit plus the current digit. Look very carefully at the return reverse....statement.

I would suggest running this by hand with pen and paper and e.g. called with "123".

• n%10means the remainder of n divided by 10.
• n/10means the integer result of n divided by 10.

Answer 3

The simple way to think about this is to create a variable flow, as follows:

reverse(123);
-> return reverse(123,0);
-> n!= 0, so call reverse(123/10,0*10+(123%10)) -> reverse(12,3);
-> n!= 0, so call reverse(12/10,0*10+(12%10)) -> reverse(1,32);
-> n!= 0, so call reverse(1/10,0*10+(1%10)) -> reverse(0,321);
-> n=0, return 321;

So you can see how 123 is converted to 321.

Answer 4

This function takes n, removes the rightmost digit. It then shifts r to the left and adds the new digit. When there are no more digits to remove in n (n == 0), it means that the complete number is reversed so it can be returned.

Answer 5

the variable r contains the running result - each time reverse(n,r) is called, the r passed in is the result so far.

with each iteration, n is divided by 10. this removes the lowest decimal place from the number. for example, if you had 306, the result would be 603, so he algorithm strips off 6, places it on the result, then strips off 0, puts that on the result, and strips off 3 and puts it on the result.

with each iteration, r is multiplied by 10, thereby shifting the decimal value left one place (36 becomea 360) and adding the lowest remaining decimal place from n to r (n%10).

hope this helps.

Answer 6

I find the easiest way to properly understand recursion is to try to work it through on paper.

reverse(1234, 0)
-- n = 1234/10, r = 10*0+1234%10
reverse(123, 4)
-- n = 123/10, r = 10*4 + 123%10
reverse(12, 43)
-- n = 12/10, r = 10*43 + 12%10
reverse(1, 432)
-- n = 1/10, r = 10*432 + 1%10
reverse(0, 4321)

this final condition will send 4321 back to the root of the recursion and 4321 will be the answer.

Answer 7

r isn't used at all

It's used in the 'two argument' reverse method. 10*r+n%10

That's a pretty tricky thing, actually, and pretty cool.

This is a great example of how poorly named variables make it difficult to understand the code. We have 3 lines of code that actually do something, and it's not real obvious how it works.

Here's the same code (with the exception of a constant) with different variable names:

private static int NOTHING_REVERSED_SO_FAR = 0;
private static int reverse(int numberToBeReversed, int reversalSoFar) {
    if (numberToBeReversed == 0) return reversalSoFar;
    return reverse(numberToBeReversed/10, 10*reversalSoFar + numberToBeReversed%10);
}
public static int reverse(int numberToBeReversed) {
   return reverse(numberToBeReversed, NOTHING_REVERSED_SO_FAR);
}

So we invoke the public method initially. Say we pass 123 as the numberToBeReversed. This invokes the private version passing the 123 unchanged and initializing the reversalSoFar to 0.

So straight away, you see if numberToBeReversed is 0, we return whatever it is we've calculated so far. I recommend you write a junit test that challenges his assertion.

So when we recurse, what are we actually doing? First, not that we are not really dividing numberToBeReversed by 10. We're doing the division, and passing the result recursively. numberToBeReversed is not being changed.

The result of the division is 123 -> 123/10 -> 12. (Being an int data type, the fraction is lost.) ok, so we're passing a 12 as the first argument. Now what of the 2nd argument. We know we passed reversalSoFar a 0. So we have 10*(0)+(123)%10. 123 is correct here since we didn't change numberToBeReversed. The result is 3. So we're going to recurse again, passing a 12 and a 3.

Now, you do the next iteration.

0.   123  0
1.   12   3
2.   ??   ?