我被合并排序递归部分困住了。
void divide(int arr[], int low, int high) {
int mid;
if(low < high) {
mid = (low + high)/2;
divide (arr, low, mid);
divide (arr, mid+1, high);
numbersSort (arr, low, mid, high);
}
}
假设数组大小为四。第一次它会被 divide(arr,0,4)
调用然后 divide(arr,0,2)
, divide(arr,0,1 )
, divide(arr,0,0)
分别。
但是有一句话要说,当谈到 divide(arr,0,0)
时,它应该在 low < high 条件下停止。那么 divide 和 numberSort()
函数是如何工作的呢?
我还有一个问题要问,numberSort() 什么时候起作用? 如果你能通过模拟上面的代码逐行给我,我将不胜感激。我对此感到非常 panic 。 提前谢谢。
最佳答案
Then how is it work for divide and numberSort() function?
当您调用另一个函数时,给定函数的执行不会停止,它只会暂停直到该函数返回。假设您当前正在执行 divide(arr,0,1)
。 low
仍然小于 high
,因此您输入条件并调用 divide(arr,0,0)
,它将执行所需的任何操作做(提示:尽量不要担心它刚才做了什么),然后你调用 divide(arr,1,1)
再次做它的事情并返回。接下来,您调用 numbersSort(arr,0,0,1)
,它将数组的两个部分重新组合,结果是数组从索引 0 到索引 1 排序。
到目前为止还好吗?好吧,好吧,接下来你就回来吧。碰巧我们刚才谈到的 divide(arr,0,1)
调用是由 divide(arr,0,2)
调用调用的,所以当 divide(arr,0,1)
返回,divide(arr,0,2)
的执行从 divide(arr,0,1) 之后的点继续
。所以接下来发生的事情将是 divide(arr,2,2)
调用,对吧? 2 不小于 2,所以它也立即返回,然后你点击 numbersSort(arr,0,1,2)
,它组合了数组的两个部分(即 0到 1,以及 2 到 2) 到从 0 到 2 的正确排序的数组中。现在数组从索引 0 到索引 2 排序。
但是,当然,divide(arr,0,2)
是在 divide(arr,0,4)
调用的上下文中调用的,所以当divide(arr,0,2)
返回接下来发生的事情是 divide(arr,3,4)
。让我们假设它做了正确的事情并将数组从索引 3 排序到索引 4。然后您将进入 numbersSort(arr,0,2,4)
,它结合了数组并返回到任何名为 divide(arr,0,4)
的函数。
一开始肯定很难理解递归。坚持下去——它最终会成功的。如果您可以在调试器中单步执行一个小型示例的代码,那可能会帮助您了解发生了什么。此外,研究纸上的代码也会有所帮助。尽量不要陷入同时理解它在每个级别如何工作的困境,而是寻找在单个级别发生的事情,并相信调用任何函数(甚至递归调用)都会做正确的事情。
关于c++ - 递归部分解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33187711/