合并排序函数中的两个递归调用混淆
我已经与算法脱节了一段时间,这些天开始修改我的概念。令我惊讶的是,我对递归技能的最后记忆是我擅长它,但现在不行了。所以,我有一个基本问题要问你们,这让我感到困惑。请先查看以下代码..
private void mergesort(int low, int high) {
if (low < high) {
int middle = (low + high)/2 ;
System.out .println ("Before the 1st Call");
mergesort(low, middle);
System.out .println ("After the 1st Call");
mergesort(middle+1, high);
System.out .println ("After the 2nd Call");
merge(low, middle, high);
}
}
函数调用
mergesort(0,7);
输出是
第一次通话前
第一次通话前
第一次通话前
第一次通话后
第二次通话后
第一次通话后
第一次通话前
第一次通话后
第二次通话后
第二次通话后
第一次通话后
第一次通话前
第一次通话前
第一次通话后
第二次通话后
第一次通话后
第一次通话前
第一次通话后
第二次通话后
第二次通话后
第二次通话后
在上面的代码和结果中,让我感到困惑的是第二个递归调用。我正在理解流程,直到第四条输出线(即:在第一次调用之后)。但我不明白为什么它输出(在第二次呼叫之后)之后(在第一次呼叫之后)。根据代码的理解,在输出之后(第一次调用之后),应该调用带有参数(middle+1,high)的mergesort函数,它应该输出(在第1次调用之前),并使用mergesort(低,中)进入递归调用。我与一个递归调用函数兼容,并理解并与前斐波那契示例同步。