这里是合并排序中分区的代码..我无法真正理解 recusrion 在其中是如何工作的!!
合并排序分区
void partition(int arr[], int low, int high){
int mid;
if(low < high){
mid = (low + high)/2;
partition(arr, low, mid);
partition(arr, mid + 1, high);
mergeSort(arr, low, mid, high);
}
}
实际上我在许多递归问题中都被搞砸了,我无法理解系统堆栈在递归中是如何工作的……
我是初学者..
我会尽力使递归函数对您来说更简单。以一个阶乘伪代码的小例子为例:
int fact(n)
{
if(n==1 || n==0) return 1;
else
return (n*fact(n-1));
}
这将做的是创建一堆函数。假设我调用 fact(3)
这将生成如下堆栈:
fact(0)
fact(1)
fact(2)
fact(3)
将每个函数压入堆栈的位置。首先调用 fact(3)
。 fact(3)
调用 fact(2)
。所以在通过之后——
堆栈构建:
fact(0)
fact(1) fact(1)
fact(2) fact(2) fact(2)
empty --> fact(3) ---> fact(3) --> fact(3) --> fact(3)
现在函数捕获 n=0
并返回 1
。现在功能开始涌现。
堆栈:
fact(0) -----> (returns 1) = 1
fact(1) -----> (returns 1) * 1 (1's popped out)
fact(2) -----> (returns 2) * 1 (1 is actually 1*1)
fact(3) -----> (returns 3) * (2 = 2*1*1)
----->6
编辑:添加弹出功能。至于排序堆栈,请查看@P0W 的回答。
试着举一个小例子来构建你的堆栈。然后转向复杂的。记住练习是关键。这就是递归函数作为堆栈工作的方式。
希望对您有所帮助。 :)