为什么递归对递归调用的不同放置采取不同的行为

Question

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

代码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,打印4,依此类推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,依此类推.但事实显然并非如此.

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

Answer 1

在第一种情况下,完成打印然后调用.

在第二种情况下,调用以这种方式发生:

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)