mergesort中的递归：两个递归调用 [英] recursion in mergesort: two recursive calls

问题描述

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

我理解当如果statement为false，则退出方法/函数。例如，如果我在main方法中调用 mergesort（0,5），则第一个 mergesort（低，中）将运行3次并终止，然后该程序将转到第7行。

I understand the fact that when the if statement is false you exit the method/function. For example, if i call mergesort(0, 5) in the main method the first mergesort(low, middle) will run 3 times and terminate, then the program will go to line 7.

我感到困惑的是为什么高 mergesort（中间+ 1，高）; 第5行时，c>突然从0变为1。

What i am confused about is why high suddenly turns from 0 to 1 when the program goes back tomergesort(middle+1, high); in line 5.

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

here is another example of a similar but simpler program

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行的递归（i + 1）; 将运行3次，直到if语句为false，然后它将转到第6行，然后程序将转到第4行递归（i-1）; 然而， i 突然从3变为2，当它从第6行变为第4行时。这是我最容易混淆的。为什么在调用第二个递归方法时我变成2。

this time if i call recursionExample(0) line 3's recursion(i+1); will run 3 times until the if statement is false, then it will go to line 6, then after that the program will go to line 4 recursion(i-1); However, i suddenly turns from 3 to 2, when it goes from line 6 to line 4. This is what i find most confusing. Why does i turns into 2 when the second recursive method is called.

推荐答案

关于你的第二个片段：

public static void recursionExample(int i){     
    if(i < 3){                                 
        recursionExample(i+1);  // this is called for the last time when i==2, i.e. 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
    }                                         
} 

这篇关于mergesort中的递归：两个递归调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！