Why does recursion return the first call in the stack and not the last?

Question

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.

• candied_orange: 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.
• Andy: 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.
• Martin Maat: Short answer: you probaly meant to code "i = incrementI(i + 1);" rather than "incrementI(i + 1);"
• Weaver: 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.
• gnat: 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..."

Answer 1

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.

• Basile Starynkevitch: Wikipedia's call stack page has a nice and very relevant picture.

Answer 2

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.

Answer 3

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.

For other values it 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.

• Eiko: This is not an identity function. Hint: incrementI(6) will just lead to a stack overflow.
• coredump: @Eiko I was already editing the answer. Thanks anyway.

Answer 4

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.

Answer 5

++indent = in new call

--indent = in previous call

1st case

incr (0)
 incr (1)
 incr (2)
 incr (3)
 incr (4)
 incr (5)
 return 5
 return 4 
 return 3 
 return 2
 return 1
return 0

2nd case

incr (0)
 incr (1)
 incr (2)
 incr (3)
 incr (4)
 incr (5)
 return 5
 return 5 
 return 5 
 return 5
 return 5
return 5

if i is assigned to the returned result then i will be initialised with the returned value e.g. 5 and this will be repeated till the last return

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

which in the call stack will look like:

(0 + 1)
 (1 + 1)
 (2 + 1)
 (3 + 1)
 (4 + 1)
 incrementI(5)
 i == 5 is true
 return i; //i is 5
 i = ^ 
 return i; //i is 5
 i = ^ 
 retrun i //i is 5
 i = ^
 return i //i is 5
 i = ^
 return i //i is 5
i = ^
return i //i is 5

Assigning i to the result of incrementI(i) works as first is evaluated the right side of the assignment e.g. incrementI(i) and then the result is assigned to i.

incrementI() is no more evaluating (i+1), this was already done and the decision of the if-else statements taken, now all stack calls of the function are at their return statement phase. We got 6 i's (form 0 to 5) and each i from the call stack above returns value which initialises the i in the call stack below. All they do is passing the final value to each other.