当有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