有人可以引导我完成这段代码的 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- 12. System.out.print("A");3. testMethod(1); // 2 - 14. System.out.print("B");`现在让我们考虑子调用 testMethod(1) n=1 > 0, stack for testMethod(1); =>testMethod(0); // 1-1System.out.print("A");testMethod(0); // 1 -1System.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 这个调用什么也不做，所以回到testMethod1testMethod1打印 A用0调用testMethod3，所以什么也没有发生，然后再次 返回testMethod1 testMethod1打印 B 现在我们回到原来的testMethod调用A 被打印，现在我们再次做同样的事情，所以 AB 被打印，最后 B