0

我试图了解递归是如何工作的。由于递归调用的放置，我有两个具有不同输出的代码。我知道应该有不同的输出，但我不明白为什么输出是这样的。

代码 1（打印后进行递归调用）：

public class Test {
    public static void main(String[] args) {
        xMethod(5);
    }

    public static void xMethod(int n) {
        if (n > 0) {
            System.out.print(n + " ");
            xMethod(n - 1);
        }
    }
}

上面的输出是 5 4 3 2 1。我明白为什么我会得到这个输出。这是因为首先打印5，然后将5减去1，然后打印4，以此类推。

我不明白的是以下代码的输出，当递归调用位于打印之前。

代码 2（在打印之前进行递归调用）：

public class Test {
    public static void main(String[] args) {
        xMethod(5);
    }

    public static void xMethod(int n) {
        if (n > 0) {
            xMethod(n - 1);
            System.out.print(n + " ");
        }
    }
}

上面的输出是 1 2 3 4 5。我不知道为什么会得到这个输出。我会想象输出是 4 3 2 1，因为减去 5，然后打印为 4，依此类推。但这显然不是这样的。

有人可以帮助我了解递归过程中发生了什么吗？

4

4 回答 4

5

在第一种情况下，打印完成，然后调用。

在第二种情况下，调用以这种方式发生：

x(5) -> x(4) -> x(3) -> x(2) -> x(1) -> print(1) ->print(2) ->print(3) ->print(4) -> print(5)

打印从结束通话开始。

x(5)
  |
  x(4)                            print(5)
    |                             | 
    x(3)                    print(4)
      |                     |
      x(2)            print(3)
        |             |
        x(1)    print(2)
          |     | 
          print(1)

在第一次的情况下

  print(5)
  x(5)
  |
  print(4)
  x(4)                            
    |
    print(3)                             
    x(3)                    
      |
      print(2)                     
      x(2)            
        | 
        print(1)  
        x(1)
于 2013-09-07T06:59:31.623 回答
1

我已经列出了您的第二个片段的执行流程的堆栈跟踪（希望我可以更好地对齐表格和 4 列）

如果您在调试程序时单步执行程序，您将获得一个类似的堆栈跟踪，该堆栈跟踪会在您单步执行程序的执行流程时告诉您变量的值，列表类似于下面列出的信息：

堆栈跟踪| 变量 n 的值 | 执行的语句 | 输出

   主要的
    xmethod(5) 5 xmethod(4)
     xmethod(4) 4 xmethod(3)
      xmethod(3) 3 xmethod(2)
       xmethod(2) 2 xmethod(1)
        xmethod(1) 1 xmethod(0)
         xmethod(0) 0               
        xmethod(1) 1 System.out.print(1 + " ") 1
       xmethod(2) 2 System.out.print(2 + " ") 1 2
      xmethod(3) 3 System.out.print(3 + " ") 1 2 3
     xmethod(4) 4 System.out.print(4 + " ") 1 2 3 4
    xmethod(5) 5 System.out.print(5 + " ") 1 2 3 4 5

您应该阅读本教程 ( http://www.vogella.com/articles/EclipseDebugging/article.html ) 以掌握调试的窍门。调试程序将帮助您抢先解决类似这样的查询，您自己。

于 2013-09-07T08:44:21.010 回答
1

在第二个代码中，行： System.out.print(n + " ");除非所有递归调用都完成，否则不会执行。

递归函数在执行打印行之前调用自身。

于 2013-09-07T07:04:19.357 回答
1

在第一个脚本中，

public static void xMethod(int n) {
    if (n > 0) {
        System.out.print(n + " ");
        xMethod(n - 1);
    }
}

在进入递归调用的步骤之前打印输出。

在第二个脚本中，

public static void xMethod(int n) {
    if (n > 0) {
        xMethod(n - 1);
        System.out.print(n + " ");
    }
}

该函数不断地“进入”递归，即一旦调用 xMethod(n-1)，它下面的行就不会执行，即 print 语句。这种情况一直发生，直到最后一个递归调用被执行，即当 x == 1 时，然后调用返回并开始所有打印语句，从 x == 1 的打印语句开始，然后是 x == 2 的打印语句等等，直到第一次调用的最后一个打印语句。

于 2013-09-07T07:05:12.843 回答