Por que a recursão retorna a primeira chamada na pilha e não a última?

A chave aqui é empilhar quadros . Vamos dar uma olhada no seu primeiro exemplo:

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

Na chamada primeiro , você tem uma variável chamada i , com o valor de 0 . Como i não é 5, ele chamará incrementI novamente com 1 .

Desta vez, você tem um novo quadro de pilha e uma variável diferente chamada i . Toda vez que você chama incrementI , um novo i está sendo criado com o novo valor.

Quando você chama incrementI 6 vezes, cada chamada de função tem sua própria cópia de i :

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

A função top retorna 5 (como isso é i ), e então a próxima função retorna 4 (já que é sua cópia de i ), até o final função retorna 0 .

No seu segundo exemplo, ocorre a mesma coisa, exceto que cada função está retornando a função acima retornada. Portanto, a função top retorna 5 , então a próxima função retorna 5 ( como é o que a função anterior retornou), e assim por diante.

Vamos analisar o primeiro snippet de código e fazer uma análise de caso.

Quando i == 5

O primeiro trecho de código é equivalente a:

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

Caso contrário

Se, no entanto, i for diferente de 5, o código será equivalente a:

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

Sua função não tem efeito colateral, exceto chamar a si mesma. Pode não terminar se você começou acima de 5, mas este não é o caso em seu exemplo. Assumindo que o código não é chamado de nenhum outro lugar, e com alguma prova indutiva, o código é o mesmo que:

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

Conclusão

Em ambos os casos, seu código simplesmente retorna sua entrada, é quase como a função de identidade, exceto que ele poderia empilhar o estouro.

A resposta de Nathan Merrill está correta, e esta é a maneira padrão de descrever a situação.

Outra maneira de descrever a situação é imaginar que toda vez que uma função é chamada, uma cópia da função é feita naquele ponto , com todos os formals < em> substituído por seus valores . (Isto ignora o fato inteiramente relevante de que formals são variáveis . Vamos fingir por um momento que eles não são.)

Além disso, quando um if é avaliado, se a condição for verdadeira, o if é substituído pela consequência e, se for falso, é substituído pela alternativa.

Você chama incrementI(0) para que esse código apareça:

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

O que acontece? 0 == 5 é falso, então isso é equivalente ao código:

incrementI(0 + 1);
return 0;

Se a chamada retornar, 0 será retornado. Se a chamada falhar, o programa trava. Se a chamada for interrompida, o programa trava. Vamos supor que a chamada retorne normalmente; portanto, o método retorna 0.

Agora, suponha que você passe 5. Isso faz com que esse código "apareça magicamente"

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

5 == 5 é verdadeiro, então isso é equivalente a

return 5;           
return 5;

Então, agora, deve ficar claro por que seu método retorna o que ele faz com os argumentos.

Esse tipo de "raciocínio equacional" é mais comumente usado em linguagens de programação funcionais como Haskell ou ML, mas é uma técnica de raciocínio bastante decente mesmo em linguagens como Java, desde que você não mude um formal.

Para entender o que está acontecendo, você precisa entender o seu bug - em uma ramificação do seu if, você não altera o que é retornado.

Seu primeiro exemplo pode ser substituído por:

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;
}

Ou com isso:

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;
}

A recursão tem dois propósitos: calcular um valor baseado em uma SEQUÊNCIA de entradas ou atuar sobre os elementos em uma sequência. Qualquer chamada para uma função recursiva que não tome medidas, nem calcule e retorne um valor, pode ser ignorada como sem propósito.