c - 多次递归语句调用

Question

void quickSort(int *a, int beg, int end)
{                       
  int pivotLoc;

  if (beg < end)
  {         
    partitionArray(a, beg, end, &pivotLoc);       
    quickSort(a, beg, pivotLoc - 1); 
    quickSort(a, pivotLoc + 1, end);
  } 
}

什么时候调用第二个递归语句？

第一个递归语句什么时候退出？

我在多次递归语句调用中遇到了很大的困惑。

你能详细说明一下吗？

Answer 1

现在让我们举一个小例子来理解递归。

假设您在以下数组上调用 quickSort:

int a = {3,1,4,2,5};
quickSort(a,0,4);

现在，让我们开始追踪。

1. 首先，您将调用 quickSort(a,0,4) 。
2. 此调用随后声明了一个局部变量 pivotLoc。
3. 然后检查条件 beg<end，其中 beg = 0 和 end = 4(如您在第 1 步中传递的那样)。
4. 现在调用一个名为 partitionArray(a,0,4,address_of_pivotLoc); 的函数
5. partitionArray 函数返回后，pivotLoc 变量的值已设置。
6. 现在您调用 quickSort(a, 0, pivotLoc-1) 再次从第一步开始重复，除了 end 不是 4，而是 pivotLoc-1。

When is 2nd recursion statement called?

答案:当条件beg<end在第一次递归调用中失败时，它只会返回。这是第二次递归调用从第一次递归的最后调用开始执行的时间(即从第一次递归没有失败条件 beg<end 的最后一次调用开始执行) .

When is 1st recursion statement exited?

答案:当它不满足条件 beg<end 时，它将到达其函数的末尾并返回到上一个相同 函数的调用。然后开始第二次递归调用。

TLDR；基本上，使 任何 quickSort 调用结束的条件是 if 条件 beg<end。