0

我正在尝试学习有关递归方法的知识，并且正在为我的二叉树编写一个方法来计算树中所有整数的总和，我的代码工作正常，但我仍然对应用程序如何知道何时停止感到困惑。我的代码如下所示：

    public int sum(){

    return sum(overallRoot);
}

private int sum(IntTreeNode root) {
    if (root == null) {
        return 0;
    }else {
        return root.data + sum(root.left) + sum(root.right);
    }

}

（上面的代码来自我的 nodeTree 类）

下一个代码来自我的主类：

public class TreeClient {

/**
 * @param args
 */
public static void main(String[] args) {
    IntTree tree = new IntTree(12);
    System.out.println(tree.sum());
}

}

所以问题是（对于许多人来说可能很简单）但是我的应用程序如何知道何时停止？我尝试使用简单的系统输出打印来弄清楚，但据我现在的理解，该方法会在无限循环中调用它自己？

希望有人有时间回复！

4

3 回答 3

3

在任何递归程序中，当达到 a 时，您的迭代将停止base condition。这里您的基本条件是：-

if (root == null) {
    return 0;
}

因此，当您的root.leftand root.right, 在 else 块中的以下return语句中都变为 null 时，您已到达您的base condition，因此您的循环停止..

return root.data + sum(root.left) + sum(root.right);
于 2012-09-30T18:59:44.580 回答
1

真的很简单

从sum函数中取一行：

return root.data + sum(root.left) + sum(root.right);

当你到达树的底部时，root.left将为空，root.right也是如此。因此，当上面的代码行调用sum(root.left)时，sum函数会落入if语句的另一半：

return 0;

因此，sum函数不再调用自身，因此停止递归

于 2012-09-30T18:59:54.837 回答
1

答案是它不会进入无限循环，因为有一个条件它不再递归调用自身。

条件是

if (root == null)

当它发生时

return 0;

而不是再次调用自己

return root.data + sum(root.left) + sum(root.right);
于 2012-09-30T19:03:14.030 回答