递归如何在For循环内工作 [英] How Recursion Works Inside a For Loop

问题描述

我不熟悉递归并试图理解此代码片段.我正在为考试而学习，这是我从斯坦福(Sandford)的CIS教育图书馆(尼克·帕兰特(Nick Parlante)的二叉树)找到的审阅者".

I am new to recursion and trying to understand this code snippet. I'm studying for an exam, and this is a "reviewer" I found from Standford' CIS Education Library (From Binary Trees by Nick Parlante).

我理解这个概念，但是当我们循环游玩INSIDE THE LOOP时，一切都变了！请帮我.谢谢你.

I understand the concept, but when we're recursing INSIDE THE LOOP, it all blows! Please help me. Thank you.

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

countTrees() Solution (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);  
}  

推荐答案

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

Imagine the loop being put "on pause" while you go in to the function call.

因为该函数恰好是递归调用，所以它的作用与您在循环中调用的任何函数相同.

Just because the function happens to be a recursive call, it works the same as any function you call within a loop.

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

The new recursive call starts its for loop and again, pauses while calling the functions again, and so on.

这篇关于递归如何在For循环内工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！