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

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.

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.

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.

++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.