有人可以引导我完成这段代码的 Java 递归过程吗？

Question

我在理解这个特定代码的递归过程时遇到了一些困难。public static void testMethod(int n){      if(n > 0){         testMethod(n-1);         System.out.print("A");         testMethod(n-1);         System.out.print("B");      }}例如，如果在我的 main 方法中输入testMethod(2);代码的输出是：ABAABB。在我的脑海中，我认为这段代码会运行直到n=0跳过该if语句，但总共运行 3 次并AB每次都输出。显然，我的想法不正确。如果有人可以引导我完成为什么会这样ABAABB而不是类似的过程ABABAB，我将不胜感激！

Answer 1

实际上，您可以逐步完成此过程，想象沿途每一步 n是什么。

也许最重要的一点是，当递归达到 1-case 时，它会打印“ AB ”，但即使它不在 1-case 中，它也会在第一次调用自身后打印A ，在调用自身后打印B第二次。因此，当我们调用 2 时，我们期望先出现 1 种情况（“ AB ”），然后是“ A ”，然后是 1 种情况（“ AB ”），然后是“ B ”。或“ ABAABB ”

testMethod(2) {

--testMethod(1) {

----testMethod(0);

----System.out.print("A");

----testMethod(0);

----System.out.print("B");

--}

--System.out.print("A");

--testMethod(1) {

----testMethod(0);

----System.out.print("A");

----testMethod(0);

----System.out.print("B");

--}

-- System.out.print("B");

}

如果您按顺序浏览打印内容，那么您将得到此输出是有意义的。

Answer 2

关键是要记住，一旦调用递归，子调用中的所有指令都会在父调用中的其余指令执行之前执行。代码中有两次对 (n-1) 的递归调用，每次打印之前一次。

让我们尝试可视化 testMethod(2) 的调用堆栈：n=2 > 0，则主堆栈为：

1. testMethod(1); // 2- 1

2. System.out.print("A");

3. testMethod(1); // 2 - 1

4. System.out.print("B");`

现在让我们考虑子调用 testMethod(1) n=1 > 0, stack for testMethod(1); =>

testMethod(0); // 1-1

System.out.print("A");

testMethod(0); // 1 -1

System.out.print("B");`

由于测试方法（0）；不执行任何操作（ 0 不 > 0）我们可以删除 testMethod(0) 以简化 testMethod(1) 的堆栈；=>

System.out.print("A");

System.out.print("B");`

现在让我们将其替换回主堆栈中的 testMethod(2) =>

1.1 System.out.print("A");//-----

                                 //-----> testMethod(1)

1.2 System.out.print("B");`//----

2. System.out.print("A");

3.1 System.out.print("A");//-----

                                 //-----> second testMethod(1)

3.2 System.out.print("B");`//----

4. System.out.print("B");`

然后按 ABAABB 的顺序打印出来

Answer 3

如果您熟悉树结构及其遍历，那么理解任何递归方法的工作过程就会容易得多。对于此方法，递归树将如下所示：

对于 n=2，完整的树如下：

现在您需要从左到右遍历树（基于中序，仅叶子），您将得到：

打印（“A”） 打印（“B”） 打印（“A”） 打印（“A”） 打印（“B”） 打印（“B”）

这是：ABAABB

Answer 4

假设您的代码行是

public static void testMethod(int n) {

    if (n > 0) {

        testMethod(n - 1);       /* line1 */

        System.out.print("A");   /* line2 */

        testMethod(n - 1);       /* line3 */

        System.out.print("B");   /* line4 */

    }                            /* line5 */

}

然后你需要执行以下步骤：

 1. n=2: line1 -> testMethod(n=1)

 2. n=1: line1 -> testMethod(n=0)

 3. n=0: line5 -> return

 4. n=1: line2 -> prints "A"

 5. n=1: line3 -> testMethod(n=0) 

 6. n=0: line5 -> return

 7. n=1: line4 -> prints "B"

 8. n=1: line5 -> return

 9. n=2: line2 -> prints "A"

10. n=2: line3 -> testMethod(n=1)

11. n=1: see 2-8

... n=1:          prints "AB"

18. n=2: line4 -> prints "B"

19. n=2: line5 -> return

Answer 5

所以第一个testMethod是用2调用的。它检查是否 2 > 0 -> true

现在让我们说得更清楚testMethod1是用1调用的 ，它检查是否 1 > 0 -> true

现在使用0调用testMethod2。

0 > 0 -> false 这个调用什么也不做，所以回到testMethod1

testMethod1打印 A用0调用testMethod3，所以什么也没有发生，然后再次 返回testMethod1 testMethod1打印 B 现在我们回到原来的testMethod调用

A 被打印，现在我们再次做同样的事情，所以 AB 被打印，最后 B