当下面的程序有2个递归语句时，如何执行递归？

我之前发布过一个问题，但我并不清楚。我的混乱很抱歉，但如果有一个项目像什么，我的意思是：当下面的程序有2个递归语句时，如何执行递归？

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和B线UNROLL或者它是如何工作（就像在编码采访书中说）？ LINE a是否一直到基本情况并返回值，然后LINE b执行？或者这两个递归语句同时归结为基本情况？

如果有人能解释水平明智的路径创建从上面的代码中的最小BST，这将是真正有助于了解如何递归多个语句（这里2-线和B线）发生

谢谢很多

来源

2012-01-07 user807496

为什么不直接按照程序流程手动？或者通过在调试器中逐步观察真实情况。 – 2012-01-07 17:50:31

[多递归展开]的可能重复（http://stackoverflow.com/questions/8770492/multiple-recursion-unrolling） – Mat 2012-01-07 17:51:01

@ Mat-我在这里再次发布它，因为我的问题因为不够清晰而关闭。 – user807496 2012-01-07 17:51:55

看着你的代码，你正在构建你的树，就像你做“深度优先搜索”一样。所以你要深入了解（在你的案例中留下），直到没有更多的元素可以处理，然后你又回到了一个层次，然后再回落。

（顺便说一句你的“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

来源

2012-01-07 19:13:50 TacticalCoder

良好的分析...现在奖励你自己一个漂亮的SO显示名称:) – Paul 2012-01-07 20:04:53

@保罗：嗯，我会尽快做到这一点:) – TacticalCoder 2012-01-07 20:16:10

该代码按顺序执行。

因此，第一次n.left被命中，它必须在下一行执行之前执行该语句。这意味着是的，它“保存”它的位置并从n.left一直沿着递归树行进，然后它有完成行n.left行然后可以继续执行（到n.right）。

来源

2012-01-07 17:52:14

user9889052做了很好的跟踪。更简单的答案是从上到下。直到返回顶级递归（在每个级别），下面的递归将不会被执行。

按照惯例我会说左边总是最上面的语句。

事实上，递归无非就是一棵树。

      Root 
        /     \ 
        RecurA    RecurB 
      /  \ 
     RecurAa  RecurAb 
     / \ 
     RAaa RAaab 
    / \ 
    dead dead

编辑当达到死（返回），它进入到右边，直到同一级别的所有节点都“死”（返回所有的递归语句），它进入返回一级，并展开RAaab。

旁边的问题：你能猜出这棵树的深度吗？这变得很明显，为什么如果子问题是不好的，递归会是有问题的。

递归在每次调用（每个级别调用）后都会生成一个堆栈帧。上一级的信息是“存储”的。当你开始弹出（当你点击返回语句时向后移动），为上一级保存的信息现在恢复。这个机制比这个简单的描述复杂得多。

MinBST起初可能不是个好主意。改为尝试这种递归。

Given an array [3,4,9,2,0,11,8,-1,2,4] 
Partition this array in halves until size of each partition is one 
Then give the sum of the left and right partition as they return (at each level)

来源

2012-01-07 19:54:58 CppLearner

当下面的程序有2个递归语句时，如何执行递归？

回答

相关问题