递归如何在For循环中工作

Question

我是递归的新手,并试图理解这段代码.我正在攻读考试,这是我从斯坦福大学的CIS教育图书馆(来自Nick Parlante的Binary Trees)找到的"评论家".

我理解这个概念,但是当我们在圈内进行递归时,一切都在吹!请帮我.谢谢.

countTrees()解决方案(C/C++)

/*
 For the key values 1...numKeys, how many structurally unique
 binary search trees are possible that store those keys.
 Strategy: consider that each value could be the root.
 Recursively find the size of the left and right subtrees.
*/

int countTrees(int numKeys) {
    if (numKeys <=1) {
        return(1);
    }

    // there will be one value at the root, with whatever remains
    // on the left and right each forming their own subtrees.
    // Iterate through all the values that could be the root...

    int sum = 0;
    int left, right, root;

    for (root=1; root<=numKeys; root++) {
        left = countTrees(root - 1);
        right = countTrees(numKeys - root);
        // number of possible trees with this root == left*right
        sum += left*right;
    }

    return(sum);  
}  

Answer 1

想象一下,当你进入函数调用时,循环被"暂停".

仅仅因为函数恰好是递归调用,它的工作方式与您在循环中调用的任何函数相同.

新的递归调用for再次开始循环,在再次调用函数时暂停,依此类推.

Answer 2

• 对于递归，在脑海中描绘调用堆栈结构会很有帮助。
• 如果递归位于循环内，则该结构类似于（几乎）一棵 N 叉树。
• 循环水平控制生成多少个分支，而递归决定树的高度。
• 树沿着一个特定的分支生成，直到它到达叶子（基本条件）然后水平扩展以获得其他叶子并返回之前的高度并重复。

我发现这种观点通常是一种很好的思考方式。