Method calling itself.. recursive?

Question

public static int m(int i, int j)    
{     
  if ( i > j)    
    return 0;    
  else    
  {
    i++;    
    m(i++, j);
  }
  return i;    
}

I had two questions. 1.) What is returned by out.print(m(3,8)); and 2.) How many times is the method m called? The answers should be 5 and 7 respectively.

When I worked out question 1, I came out with 5 but the way I did it was incorrect because the method was not called 7 times, it was only called twice. The way I did this was I went straight to the else statement since (i > j) was false at the start and method m was called again this time with (4, 8) I figured it was still false so I went back to the line where m is called and the variable i changed to 5 because of the i++ in m(i++, j). After that it would return 5 for the Value of i.

That was obviously wrong so I added some out.prints for the values of i throughout the program to see how the value was changing and it went from 3 to 9 with an out.print(i); at the beginning of method m. An out.print(i); right before return i; showed the values started to go backwards from 10 to 5 and the method was called 7 times. How does this work?

EDIT: After logging it, I was able to come up with some logic to it but I would like someone to clarify that it is correct.

method m is called with 3,8 at the start. After, it calls itself with 4,8 then 5,8....until 9,8 where the if statement becomes true and the method returns 0. It called itself 6 times so it starts go backwards or decrement-ing 6 times so since m(i++, j) is post(the i) then i becomes 10 and 10 is returned, then 9, then 8, then 7, 6, and finally 5. When it returned 10 that was 1, 9 was 2, 8 was 3, 7 was 4, 6 was 5, and 5 was 6. So since it was 6 when i = 5, that was the value that was returned. Is this correct? And if it is, a more in depth explanation would be nice to have.

Solution 1

To better understand what's happening, it might help to refactor the code as such:

public static int m(int i, int j) {
    static int calls = 0;     
    System.out.println("entering.  count: " + calls);
    calls++;

    System.out.println("i = " + i);
    System.out.println("j = " + j);

    if (i > j) { 
        System.out.println("returning 0");
        return 0;
    } else {
        i++;    
        m(i++, j);
    }

    System.out.println("returning " + i);
    return i;    
}

Note that I haven't modified any of the actual logic. All I've done is add some statements to print values, and a variable to keep track of the number of times the method is called.

Solution 2

The reason you are seeing the value decrement is because before you print the last 'i', this value is only incremented in local scope (the first i++ in your else condition).

When your m function returns to its caller, i is no longer i+1 as it was in the child, thus you see the decrementing values until the root 'm' call is returned.

Solution 3

I’ll analyze the function in general case, the specific argument values will be used at the end only. Running the function and watching what it does via debugger or debug prints is handy when you have such tools, but in certain cases you have to rely on your brain only. E.g. it is really hard to pull debug info from FPGA (you need to simulate its work). When being interviewed for a job, you typically get a computer to test the code – your analytic skills are being tested. That’s why I highly recommend using pencil & paper approach before looking at what the code really does when executed.

Question 1: Return value

When trying to analyze complicated code, knowing what you can neglect is the key to success.

Here you know that

• the code is single-threaded,
• there are no global variables, no side-effects for the world outside the current call,
• return value of the recursive call is not used.

So there is no need to think about what mess could come from other threads, you can analyze the single call without thinking of how recursive calls would influence it (apart from returning a value) and you can forget about the recursive call unless it is infinite recursion (which will not let your program terminate) because it has no effect other that consuming time.

The recursion is not infinite as i is always incremented before the recursive call and the recursion stops when i > j.

Knowing that, deciding what the return value is is pretty easy. The function can be reduced to

public static int m(int i, int j)
{
    if (i > j)
        return 0;
    else
        i += 2;
    return i;
}

Because return terminates execution of the function, this can be even further reduced to

public static int m(int i, int j)
{
    return (i > j) ? 0 : i + 2;
}

giving you the answer to question 1. When called as m(3, 8), the result is i + 2, i.e. 5, because i is less than j.

Question 2: Number of calls

The recursion is linear – at most one recursive call is made in each call. So you have to count how many calls it takes till the bottom of recursion is reached.

The bottom of recursion is the first branch of the condition. Therefore you count how many times a call is made till i > j.

j has the same value in each of the calls. There is no command to change its value, it is always passed to the recursive call unchanged. i is always incremented before the recursive call once and after the call once (i++ is postincrement, taking the effect after the original value is used). Only the first increment is relevant for the recursive call.

For the sake of counting recursive calls, the function can be reduced to

public static void m(int i, int j)
{
    if (i > j)
        return;
    else
        m(i + 1, j);
}

From this, it is obvious that i is successively incremented by 1, till it’s greater than j.

In m(3, 8), the calls are

• m(3, 8),
• m(4, 8),
• m(5, 8),
• m(6, 8),
• m(7, 8),
• m(8, 8) and
• m(9, 8).

So there are 7 of them.

If the parameters given had bigger difference, general solution would be handy. So let’s explore it. It would be quick.

If initially i > j, only one call is made, obviously. Otherwise… how many numbers do you meet when counting from i to j + 1? (j + 1) - i + 1 = j - i + 2. Plus one at the is is for the topmost call. That’s the general answer.

Comments

[Martijn Courteaux]

1) Try it. 2) Log it with a print statement.

[zapl]

There are similar questions like stackoverflow.com/questions/16095176/… that might explain the behavior.

[Oscar F]

@zapl That answered a big part of my question, thanks

[Oscar F]

I changed the code a bit from what you have but its the same logic, I just was having trouble with the calls, they were all zero the way you have it, i don't know why but I fixed that by changing m to (int i, int j, int calls) and changing out.print(m(3,8)) to (3,8,1) since the first call is there. Now what confuses me is that from what I see only one of the "i++" are incrementing the value of i. I thought it would go i,j 3,8 4,8 6,8..but it has the 5,8 though I'm not sure why

[nhgrif]

I just noticed the double i++ call. You could certainly put another System.out.println("i = " + i); call between i++; and m(i++,j);. The main point of my answer really is: When in doubt, log it a lot... (or use breakpoints).