java - 当像下面程序这样有2条递归语句时，递归是如何执行的？

Question

我之前发布了一个问题，但是我不够清楚。对于造成的困惑，我深表歉意，但我的意思是如果有这样的程序:

TreeNode createMinBST(int arr[], int start, int end) {
    if(end< start) return null;

    int mid = (start+end)/2;
    Treenode n= new Treenode(arr[mid]);
    n.left= createMinBST(arr, start, mid-1)  //LINE a
    n.right= createMinBST(arr, mid+1, end);  //LINE b
    return n;
}

LINE a 和 LINE b 是如何展开的(就像编程面试书上说的那样)或者它是如何工作的？ LINE a 是否一直执行到基本情况并返回值，然后执行 LINE b？或者两个递归语句同时下降到基本情况？

如果有人可以从上面给出的代码中解释创建最小 BST 的级别明智的路径，那么理解多个递归语句(这里是 2- 行 a 和行 b)是如何发生的将非常有帮助

非常感谢

Answer 1

查看您的代码，您构建树的方式与您进行“深度优先搜索”的方式相同。所以你要更深入(在你的情况下更深)，直到没有更多的元素要处理，然后你回到上一级，然后再返回。

(顺便说一下，您的“A 行”末尾缺少一个分号)

在学习或试图弄清楚递归调用的工作原理时，经常会出现这样的情况，打印出调用很方便。

例如，在您的情况下，如果您的起始数组包含来自 [10..24] 的数字，那么您的调用可能如下所示:

Calling minBST on 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24

    Calling minBST (left) on 10, 11, 12, 13, 14, 15, 16

        Calling minBST (left) on 10, 11, 12

            Calling minBST (left) on 10

            Calling minBST (right) on 12

        Calling minBST (right) on 14, 15, 16

            Calling minBST (left) on 14

            Calling minBST (right) on 16

    Calling minBST (right) on 18, 19, 20, 21, 22, 23, 24

        Calling minBST (left) on 18, 19, 20

            Calling minBST (left) on 18

            Calling minBST (right) on 20

        Calling minBST (right) on 22, 23, 24

            Calling minBST (left) on 22

            Calling minBST (right) on 24