Perché la ricorsione restituisce la prima chiamata nello stack e non l'ultima?

Il tasto qui è stack frames . Diamo un'occhiata al tuo primo esempio:

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

Nella chiamata prima , hai una variabile denominata i , con il valore di 0 . Poiché i non è 5, chiamerà nuovamente incrementI con 1 .

Questa volta, hai un nuovo stack frame e una diversa variabile i . Ogni volta che chiami incrementI , viene creato un nuovo i con il nuovo valore.

Quando hai chiamato incrementI 6 volte, ogni chiamata di funzione ha la sua copia di i :

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

La funzione top restituisce 5 (dato che è i ), quindi la funzione successiva restituisce 4 (dato che è la sua copia di i ), fino al fondo la funzione restituisce 0 .

Nel tuo secondo esempio, accade la stessa cosa, tranne che ogni funzione restituisce ciò che è stata restituita dalla funzione precedente. Pertanto, la funzione top restituisce 5 , quindi la funzione successiva restituisce 5 ( in quanto è ciò che la funzione precedente ha restituito), e così via.

Diamo un'occhiata al primo snippet di codice e fai un'analisi del caso.

Quando i == 5

Il primo snippet di codice è equivalente a:

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

Altrimenti

Se, tuttavia, i è diverso da 5, il codice equivale a:

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

La tua funzione non ha alcun effetto collaterale tranne chiamare se stessa. Potrebbe non terminare se hai iniziato da sopra 5, ma fortunatamente non è il caso nel tuo esempio. Supponendo che il codice non venga chiamato da nessun'altra parte, e con alcune prove induttive, il codice è lo stesso di:

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

Conclusione

In entrambi i casi, il tuo codice restituisce semplicemente il suo input, è quasi come la funzione di identità, tranne che potrebbe impilare l'overflow.

La risposta di Nathan Merrill è corretta, e questo è il modo standard per descrivere la situazione.

Un altro modo per descrivere la situazione è immaginare che ogni volta che viene chiamata una funzione, copia della funzione viene a quel punto , con tutte le formali < em> sostituito con i loro valori . (Questo ignora il fatto assolutamente rilevante che le formali sono variabili . Facciamo finta per un momento che non lo siano.)

Inoltre, quando viene valutata una if , se la condizione è vera, la if viene sostituita con la conseguenza e, se è falsa, viene sostituita con l'alternativa.

Chiama incrementI(0) in modo che appaia questo codice:

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

Che cosa succede? 0 == 5 è falso, quindi questo è equivalente al codice:

incrementI(0 + 1);
return 0;

Se la chiamata ritorna, viene restituito 0. Se la chiamata si blocca, il programma si blocca. Se la chiamata si blocca, il programma si blocca. Supponiamo che la chiamata ritorni normalmente; quindi il metodo restituisce 0.

Supponiamo ora di passare 5. Questo fa sì che questo codice "appaia magicamente"

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

5 == 5 è vero, quindi questo è equivalente a

return 5;           
return 5;

Quindi ora dovrebbe essere chiaro il motivo per cui il tuo metodo restituisce ciò che fa gli argomenti.

Questo tipo di "ragionamento equazionale" è più comunemente usato nei linguaggi di programmazione funzionale come Haskell o ML, ma è una tecnica di ragionamento abbastanza decente anche in linguaggi come Java, purché non si muti un formale.

Per capire cosa sta succedendo, devi capire il tuo bug - su un ramo del tuo se, non cambi ciò che viene restituito.

Il tuo primo esempio potrebbe essere sostituito da questo:

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

O con questo:

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

La ricorsione ha due scopi: calcolare un valore basato su una SEQUENZA di input o agire sugli elementi di una sequenza. Qualsiasi chiamata a una funzione ricorsiva che non agisce né calcola e restituisce un valore, può essere saltata come inutile.