__mergeSort递归调用的问题

Question

对递归理解的不是很透彻，

__mergeSort(int arr[],int l,int r){
	if(l>=r) return; //基线条件，结束递归调用
	int mid = l + r;
	__mergeSort(arr,l,mid);
	//这里不太理解，递归的调用顺序是怎样的,一直向下递归，然后当前函数处于等待状态？
	//等下一层的递归函数结束后再执行上层的函数？
	__mergeSort(arr,mid,r);
	——merge（arr,l,mid,r）;
}

Answer 1

liuyubobobo 2019-02-21 01:13:19

“递归的调用顺序是怎样的,一直向下递归，然后当前函数处于等待状态？等下一层的递归函数结束后再执行上层的函数？”

完全正确！其实递归函数的调用和普通函数的调用没有区别。普通函数的调用中，A函数里执行B，B执行完以后将继续执行A。递归函数也是一样的。在A函数里执行A，这个A执行完以后，要返回到上层继续执行上层的A。

具体可以参考这里：

https://coding.imooc.com/learn/questiondetail/20335.html 

https://coding.imooc.com/learn/questiondetail/43472.html

另外，值得一提的是，可以简单地使用打印的方式，配合小数据集以及单步跟踪，来帮助你更深刻的理解整个函数的执行过程，比如这样：

__mergeSort(int arr[],int l,int r){
    
    cout << "开始归并排序 [" << l << " , " << r  << "] 区间" << endl;
    if(l>=r){
        cout << "达到基线条件，返回" << endl;
        return; //基线条件，结束递归调用
    }

    int mid = l + r;
    
    cout << "准备归并排序 [" << l << " , " << mid  << "] 区间" << endl;
    __mergeSort(arr,l,mid);
    
    cout << "准备归并排序 [" << mid + 1 << " , " << r  << "] 区间" << endl;
    __mergeSort(arr,mid + 1,r);
    
    cout << "准备归并 [" << l << " , " << mid  << "] 和 [" << mid + 1 << " , " << r << "] 区间" << endl;
    __merge（arr,l,mid,r）;
}

当然，你可以把更多类似的信息放在__merge函数中。

实际使用这样的方法，去调试跟踪一个小数据量，研究一下，这些输出信息是如何，按照怎样的顺序输出的，进一步理解一下程序的执行顺序。这是非常重要的学习算法的方式哦：）

加油！：）

• 慕数据0441619 #1

  加上日志，函数执行过程确实清晰多了