c栈中的递归

这里是在merge merge中进行分区的代码。我无法理解recusrion究竟是如何工作的！

MERGE SORT PARTITION

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); } } 

实际上我在很多递归问题中搞砸了，我无法理解系统堆栈如何在递归中工作……我是一个初学者..

Answer 1

让我们举个例子

Array arr ={ 5,2,4,7,1,3,2,6}; 8个要素

  1 2 3 4 5 6 7 ^(partition+mergeSort) | +------------+ +---------------+ | | 2 4 5 7 1 2 3 6 ^ (partition+mergeSort) ^ (partition+mergeSort) | | +--+ +---+ +--+ +---+ | | | | 2 5 4 7 1 3 2 6 ^ (partition+mergeSort) ^ (partition+mergeSort) | | +---+ +---+ +---+ +---+ | | | | 5 2 4 7 1 3 2 6 4 elements 4 elements Initial Unsorted Array 

从下到上，形成两个arrays

arr[low...mid]和arr[mid+1...high]在每次递归调用时，最后它们都被合并。

只要low < high分区和合并过程就会继续

它只是mergeSort如何在这里工作的一个例子，你可以按照这个例子的代码。

在这个未排序的数组上使用partition(arr, 0,7)调用将具有：

在第一次传球mid =3 arr分为两部分使用

partion(arr,0,3)和partion(arr,4,7)

这些分区中的每一个再次分成两部分，即0到3分为(0,1)和(2,3) ，再分为(0,1)和(1,1) 。 (1,1)被跳过low > high最后2个元素与mergeSort合并

然后，一组这样的小排序数组最终合并，因为它在后续传递中从递归开始。

这里有点难以解释，在文本格式中，在纸上试试，我相信你可以弄清楚，有更小的数组，比如4个元素。

Answer 2

我会尝试让递归函数更简单。 举例说明阶乘伪代码的一个小例子：

 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 。 现在function开始弹出。

堆栈：

  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 

编辑：function添加弹出。 至于排序堆栈，请查看@ P0W的答案。

尝试一个小例子并构建你的堆栈。 然后转向复杂的。 记住练习是关键。 这就是递归函数作为堆栈的工作方式。

希望能帮助到你。 🙂