c# - 想了解多重递归的概念

Question

例如让我以归并排序为例

mergesort(int a[], int low, int high)
{
  int mid;
  if(low<high)
  {
   mid=(low+high)/2;
   mergesort(a,low,mid);
   mergesort(a,mid+1,high);
   merge(a,low,high,mid);
  }
}

在这里执行递归语句的顺序我已经阅读了一些与树结构相关的逻辑，但我很难理解它..请帮助我已经坚持了很长时间

Answer 1

它基本上是二叉树的前序遍历。

只有一个线程，所以一切都按顺序执行。所以第一次初始化mergesort函数调用自己时，同样的事情会一遍又一遍地发生，直到达到基本情况。这就是为什么在使用递归时基本情况如此重要的原因。否则你会得到无限递归，并且......堆栈溢出！

从最顶层看问题，数组的下半部分完全排序，然后上半部分完全排序，然后将这两个排序的数组合并在一起，使整个数组排序。

从下一层往下，下半部分有自己的下半部分排序，然后它的上半部分排序。这一直持续到low < high为假。在这种情况下，函数只是返回。然后第二个mergesort在mergesort调用它的那个中被调用。

如果你在纸上画出来，你会看到树从代表下半部分排序的一侧向下生长，然后返回到根部，然后向下生长到另一侧，直到它碰到基本情况并返回到根部。

Answer 2

假设a有 4 个元素。
(low, high)代表mergesort(a, low, high)。中的数字[]代表函数返回的顺序。

                     [10](0                ,                  3)
                                         /  \                           
                      [4](0    ,        1)   [8](2    ,       3)
                              / \                    / \        
                      [1](0, 0)  [2](1, 1)   [5](2, 2) [6](3, 3)
                            \         /            \        /
                            [3]merge               [7]merge
                                \                      /
                                       [9]merge

Answer 3

先进后出。

当子调用被触发时，第一个函数调用会暂停，它会等待返回值继续。

所以我会用退货单评论你的例子

mergesort(int a[], int low, int high) //fourth
{
  int mid;
  if(low<high)
  {
   mid=(low+high)/2;
   mergesort(a,low,mid); // This should be executed and returned first. it will create a chain of functions, it need to be resolved in reverse order before the program continues.
   mergesort(a,mid+1,high); // second
   merge(a,low,high,mid); //third
  }
}

然而，每个子函数都会产生它们自己的合并排序函数，这些函数将有自己的迭代。

也就是说，主归并排序会像链一样生成很多子归并排序函数，一旦链生成完成，链的最后一个环应该可以解决，即不应该满足（低

如果您有 BASIC 经验，我建议您在那里尝试，它们通常允许逐行执行，您可以“看到”代码是如何执行的。