mergesort中的递归：两个递归调用

private void mergesort(int low, int high) { //line 1 if (low < high) { //line 2 int middle = (low + high)/2 ; //line 3 mergesort(low, middle); //line 4 mergesort(middle+1, high); //line 5 merge(low, middle, high); //line 6 }} //line 7 

我理解当if语句为false时退出方法/函数的事实。 例如，如果我在main方法中调用mergesort(0, 5) ，则第一个mergesort(low, middle)将运行3次并终止，然后程序将转到第7行。

令我困惑的是当程序返回mergesort(middle+1, high);时，为什么high突然从0变为1 mergesort(middle+1, high); 在第5行。

这是一个类似但更简单的程序的另一个例子

 public static void recursionExample(int i){ //line 1 if(i < 3){ //line 2 recursionExample(i+1); //line 3 recursionExample(i-1); //line 4 } //line 5 } //line 6 

这次如果我调用recursionExample(0)第3行的recursion(i+1); 将运行3次，直到if语句为假，然后它将转到第6行，然后程序将转到第4行recursion(i-1); 然而，当它从第6行变为第4行时， i突然从3变为2，这是我最容易混淆的。 当调用第二个递归方法时，为什么我变为2。

Answer 1

关于你的第二个片段：

 public static void recursionExample(int i){ if(i < 3){ recursionExample(i+1); // this is called for the last time when i==2, ie the // last call is recursionExample(3). When that call // returns, i is still equal 2, since calling // recursionExample(i+1) doesn't change the value of the // local variable i of the current method call recursionExample(i-1); // Therefore when this line is first called, i is equal 2 } } 

Answer 2

考虑到您的第二个片段，调用顺序如下（为了便于理解，表示为树）：

 - recursionExample(0) - recursionExample(1) - recursionExample(2) - recursionExample(3), here no more recursion - recursionExample(1) ... - recursionExample(0) ... - recursionExample(-1) - recursionExample(0) ... - recursionExample(-2) ...