5

I cant for the life of me figure out why this returns 0 rather than 5. i keeps getting incremented before it hits the last return statement, however it always returns 0, from the first call in the stack. I would think that since the most recent call on the stack hits the return in the block i == 5 first it would return and print 5.

Returns 0

public static void main(String[] args) {
    System.out.println(incrementI(0));
}       


public static int incrementI(int i) {
    if (i == 5){
        return i;           
    } else {
         incrementI(i + 1);
    }
    return i;  
}

Returns 5

public static int incrementI(int i) {
    if (i == 5){
        return i;           
    } else {
        return incrementI(i + 1);
    }               
}

I'm not looking for a code fix, but rather an explanation to why recursion works this way.

  • 2
    The truth is, recursion returns the first, the last, and each one in between. The first call becomes the last return. It decides how much it cares about what the other calls got up to. You're first example calls them, then doesn't care at all about them or what they return. So the first call just returns exactly what it got. – candied_orange Oct 10 '16 at 5:58
  • 3
    Passing by value is not the same as passing by reference. It is not that recursion works that way, you simply have a bug in your code. – Andy Oct 10 '16 at 7:29
  • Short answer: you probaly meant to code "i = incrementI(i + 1);" rather than "incrementI(i + 1);" – Martin Maat Oct 10 '16 at 7:31
  • Agreeing with martain; for math-related recursion you need to do something with the return value from the recusive call. Heck, I'd say the two main recursion types are "aggregate a return value" and "do something to all nodes in a tree-like structure", the latter being where you don't care about the returns usually. – StarWeaver Oct 10 '16 at 10:24
  • please don't cross-post: stackoverflow.com/questions/39949767/… "Cross-posting is frowned upon as it leads to fragmented answers splattered all over the network..." – gnat Oct 10 '16 at 11:36
17

The key here is stack frames. Lets take a look at your first example:

public static int incrementI(int i) {
    if (i == 5){
        return i;           
    } else {
         incrementI(i + 1);
    }
    return i;  
}

On the first call, you have a variable named i, with the value of 0. Since i isn't 5, its going to call incrementI again with 1.

This time around, you have a new stack frame, and a different variable named i. Every time you call incrementI, a brand new i is being created with the new value.

When you've called incrementI 6 times, each function call has its own copy of i:

 incrementI: 5
 incrementI: 4
 incrementI: 3
 incrementI: 2
 incrementI: 1
 incrementI: 0

The top function returns 5 (as that is i), and then the next function returns 4 (as that is its copy of i), until the bottom function returns 0.

In your second example, the same thing occurs, except each function is returning what the above function returned. Therefore, the top function returns 5, then the next function returns 5 (as that is what the previous function returned), and so on.

5

Let's look at the first snippet of code and do a case analysis.

When i == 5

The first snippet of code is equivalent to:

public static int incrementI(int i) {
    return i;           
}

Otherwise

If, however, i is different from 5, then the code is equivalent to:

public static int incrementI(int i) {
    // if (i == 5){
    //    return i;           
    // } else {
         incrementI(i + 1);
    //}
    return i;  
}

Your function has no side effect except calling itself. It might not terminate if you started from above 5, but this is fortunately not the case in your example. Assuming the code is not called from anywhere else, and with some inductive proof, the code is the same as:

public static int incrementI(int i) {
    return i;  
}

Conclusion

In both cases, your code simply returns its input, it is almost like the identity function, except that it could stack overflow.

  • This is not an identity function. Hint: incrementI(6) will just lead to a stack overflow. – Eiko Oct 10 '16 at 7:28
  • @Eiko I was already editing the answer. Thanks anyway. – coredump Oct 10 '16 at 7:30
5

Nathan Merrill's answer is correct, and this is the standard way of describing the situation.

Another way to describe the situation is to imagine that every time a function is called, a copy of the function is made at that point, with all the formals replaced with their values. (This ignores the entirely relevant fact that formals are variables. Let's pretend for a moment that they are not.)

Furthermore, when an if is evaluated, if the condition is true then the if is replaced with the consequence, and if it is false, then replaced with the alternative.

You call incrementI(0) so that makes this code appear:

if (0 == 5){
    return 0;           
} else {
     incrementI(0 + 1);
}
return 0;

What happens? 0 == 5 is false, so this is equivalent to the code:

incrementI(0 + 1);
return 0;

If the call returns, then 0 is returned. If the call crashes then the program crashes. If the call hangs, then the program hangs. Let's assume that the call returns normally; therefore the method returns 0.

Now suppose you pass 5. That causes this code to "magically appear"

if (5 == 5){
    return 5;           
} else {
     incrementI(5 + 1);
}
return 5;

5 == 5 is true, so this is equivalent to

return 5;           
return 5;

So now it should be clear why your method returns what it does given the arguments.

This sort of "equational reasoning" is more commonly used in functional programming languages like Haskell or ML, but it is a pretty decent reasoning technique even in languages like Java, provided that you do not mutate a formal.

1

To understand what is going on, you need to understand your bug -- on one branch of your if, you don't change what is returned.

Your first example could be replaced with this:

public static void main(String[] args) {
    System.out.println(incrementI(0));
}       


public static int incrementI(int i) {

  if (i==0){
    incrementI(1);
    incrementI(2);
    incrementI(3);
    incrementI(4);
    incrementI(5);
  }

  return i;
}

Or with this:

public static int incrementI(int i) {
    if (i==0){
     // incrementI(1); line commented out, it had no effect on result
     // incrementI(2); line commented out, it had no effect on result
     // incrementI(3); line commented out, it had no effect on result
     // incrementI(4); line commented out, it had no effect on result
     // incrementI(5); line commented out, it had no effect on result
    }
    return i;
}

Recursion has two purposes: to calculate a value based upon a SEQUENCE of inputs, or to act upon the elements in a sequence. Any call to a recursive function which neither takes action nor calculates and returns a value, can be skipped as serving no purpose.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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