递归调用 与 递归调用后面的部分 的关系不太清楚

Question

template<typename T>
void __mergeSort(T arr[], int l, int r)
{
	if (l >= r)
		return;

	int middle = (l + r) / 2;
	__mergeSort(arr, l, middle);
	__mergeSort(arr, middle + 1, r);
	__merge(arr, l, middle, r);
}

老师， 整个过程我理解了，但是，在  __mergeSort（） 函数中分别使用了两个递归调用函数，对这个递归过程还是有一点模糊，你能不能在8个数据的数组例子中解释一下 这个两个递归调用函数 与  __merge()  之间运行关系

Answer 1

liuyubobobo 2017-05-25 17:43:49

__mergeSort在最初会不断的细分整个数组，当数组的长度为1，即整个数组不需要排序也是有序的情况下开始进行__merge，将两个包含有1个元素的数组merge成了一个有序的2个元素的数组；之后将两个有序的包含2个元素的数组合并成一个有序的包含4个元素的数组；之后将两个有序的包含4个元素的数组合并成一个有序的包含8个元素的数组...依次类推。

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

如果对这个过程的细节感觉理解的还不透彻，不要只对着代码生想。实际使用一个小数据量的测试用例，比如只包含8个元素的无序数组，然后使用debug一步一步跟着程序走一遍，观察程序在运行每一行代码之后数据和各种辅助的变量具体是怎样变化的，看看和自己的理解是否有偏差。这是非常好的理解算法运行机制的形式。千万不要怕麻烦！踏踏实实拿一张纸一根笔，找一个下午做一遍这个事情，是绝对值得的。

加油！