1

I was stepping through this code below and the part that I do not understand is how "Leaving" n value becomes 2,5 and 10. I understand the first part of recursive calls till n==0, and return takes the control to move to the else part and print (0%2). Shouldn't the program halt after that?

void fun2(int n){
    System.out.println("Entering"+n);
    if(n==0)
        return;
   else{
        fun2(n/2);
        System.out.print("Leaving"+n+"---->");       
        System.out.println(n%2);
    }
}

Output :

      Entering5
      Entering2
      Entering1
      Entering0
      Leaving1---->1
      Leaving2---->0
      Leaving5---->1
      Leaving10---->0
5
  • 1
    It's one way to debug. Another way is to simply step through line-by-line in a debugger. Jul 8, 2013 at 1:50
  • Also, how does the behaviour of this code differ from what you were expecting? Jul 8, 2013 at 1:52
  • I have no idea of how leaving gets the values of "n" of entering. I've hardly had to use recursion so tracing this seems a fairly confusing task. Could you explain? This is not my code. I just added the prints Jul 8, 2013 at 1:55
  • A recursive function call is no different to any other function call. If funcA() calls funcB(), the values in the scope of funcA() are retained until funcB() returns. Exactly the same occurs in a recursive call situation. Jul 8, 2013 at 2:01
  • Im sorry I still dont seem to get it. This part of the output is what is confusing. The return causing the control to enter the else part with n=1 and printing seems to be all I can trace to. After that the control again returns the print statements of the else part causing to print this Leaving2---->0 Leaving5---->1 Leaving10---->0 Why does this happen. Jul 8, 2013 at 2:05

1 Answer 1

1

First of all, I believe that you have an error in your output. When I run the above code by calling fun2() with a value of 5, I get all of the output that you've indicated except the line Leaving10---->0. Are you sure that this is in the output of the fun2() function or perhaps an artifact from the code location where you call fun2()? Perhaps you're calling the fun2() function with a value of 10, and left off the first first line of output Entering10?

This function works by calculating the value of each binary digit. This is done using the % operator, known as the modulo operator (also known as the remainder operator) in the final line of the else block: System.out.println(n%2);

101 = (1*2^2) + (0*2^1) + (1*2^0) = 4 + 0 + 1 = 5

Each iteration calculates the next lower power of 2 because it's called with n/2. Bear in mind that you're dealing with integer division here, so there is no remainder. 1/2 = 0, not 0.5. However, the integer modulus function will work just fine, so 1%2 = 1 (1 divided by 2 = 0 with a remainder of 1).

Here's a detailed look at each recursion level of the method:

  1. n = 5, n/2 = 2, fun2(2), n%2 = 1
  2. n = 2, n/2 = 1, fun2(1), n%2 = 0
  3. n = 1, n/2 = 0, fun2(0), n%2 = 1
  4. n = 0, method returns

When you put the individual console output together, you get 101, which is binary for 5.

If you were to have called fun2() with a parameter value of 10, you would have seen the output 1010:

1010 = (1*2^3) + (0*2^2) + (1*2^1) + (0*2^0) = 8 + 0 + 2 + 0 = 10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.