如果我将一个递归调用除以另一个，我会得到一个无限循环吗？

Question

我正在试验 Java 中的递归，我有这个方法：

public static int recursion(int n) {
    if(n==1) {
        return 2;
    } else {
        int test = (recursion(n-1))/(recursion(n-1));
        return test;
    }
}

如果我用 运行它n = 50，它永远不会打印任何东西，所以我猜递归调用是无限的？有人能解释一下为什么吗？

Answer 1

它不是无限的，只是巨大的。您将执行大约 2^50 次递归调用。即使每次调用只需要一纳秒（这太低了），这也意味着总运行时间约为两周。

Answer 2

这里，recursion()被称为二叉树

recursion(50) -> recursion(49) -> recursion(48) ...
                                  recursion(48) ...
                 recursion(49) -> recursion(48) ...
                                  recursion(48) ...

因此，二叉树的高度为49
然后recursion()叫：树的节点总数倍。这相当于2^(h+1)-1= 2^(49+1)-1= 2^(50)-1 次。
这是巨大的，需要很长时间来执行。这是问题，但不是无限的。

您可以改为执行以下操作，这不是问题，因为recursion(n)torecursion(n-1)仅被调用一次：

public static int recursion(int n) {
    if(n==1) {
        return 2;
    } else {
        int test = recursion(n-1);
        test = test/test
        return test;
    }
}