递归 - mystery1

Question

在使用下面的代码时遇到困难，我正确地接听了第一个电话，因为条件立即正确。然而，第二次调用 4 让我很困惑，我得到了答案 2, 1 但是它是不正确的 - 我显然把事情搞混了。有人能准确地向我解释为什么我的答案是错误的，以及这个例子中递归跟踪过程的正确分解。我确实理解递归的元素，但是我在跟踪过程中遇到问题。

public void mystery1(int n) {
    if (n <= 1) {
        System.out.print(n);
    } else {
        mystery1(n / 2);
        System.out.print(", " + n);
    }
}

mystery1(1);
mystery1(4);
mystery1(16);

Answer 1

当你调用 mystery1(4) 时，它会转到 else 部分并调用 mystery1(2)，因为 n>1。 print语句只有在mystery1(2)执行完后才会执行。

同样的事情发生在 mystery1(2) 上，它调用 mystery1(1)。它等待 mystery(1) 完成执行。

调用 mystery1(1) 时，它会打印“1”。

然后，mystery1(2) 将继续打印“,2”。

最后，mystery1(4) 将继续打印“,4”。

所以你的输出将是 1,2,4

Answer 2

递归既美丽又非常强大，当观察它时，人们会被骗。

让我向您解释一下我在准备 GATE（工程学研究生能力测试）时是如何学习它的。

将每个函数调用视为 2 个部分：

打印
调用自身减半

现在所有操作都将堆叠在旧操作上，直到我们退出递归并且函数循环中只剩下 Printing 为止。我们将以堆栈格式打印出来 i.e FIFO

例如，如果我们在堆栈中有这些元素：

顶部： 4个 3个 7 2个底部

它将打印 4 3 7 2 .

现在回答你的问题：

让我们把你的条件语句分成两半，1st 将是 if condition with Print 2nd 将是 else 及其 print.

注意：只有一部分，即 1st 将打印 1，并且也没有逗号 (,)。

我附上了下面的图片，请参考它，认为打印语句在堆栈上，并且最底层的打印语句将首先执行，因为我们将结束函数调用。

现在组合 mystery1(1),mystery1(4),mystery1(16) 最终输出将是：1 1个 , 2 , 4 1个 , 2 , 4 , 8 , 16

PS：如果您要接受 Amazon 、Google 或任何知名产品公司的采访，他们会提出带有递归味道的问题，而且也不会使用任何编译器，他们都想通过编程来测试你的概念。

Answer 3

在你的方法中：

public static void mystery1(int n) {
    if (n <= 1) {
        System.out.print(n);
    } else {
        mystery1(n / 2);
        System.out.print(", " + n);
    }
}

尝试在 mystery1(n / 2); 调用之前替换 System.out.print(", " + n); 的位置。

在第一种情况下，当 System.out 在 mystery1 调用之后，你得到的结果是 1, 2, 4，因为，首先你必须得到结果，然后打印它。

在第二种情况下，当 System.out 在 mystery1 调用之前，结果为 , 4, 21，因为，首先打印结果，然后在函数中计算下一个结果。

递归 - mystery1

Recursion - mystery1

java

recursion

trace