Java递归：示例

Question

我知道recursion是如何工作的，即：

method calls itself until it reaches a base case then it can start solving its problem.

在这个代码示例中，是一个从花瓶中移除花的方法

我添加了一个跟踪语句，以便能够在每次通话后看到花瓶中有多少花。然而，输出在花瓶中留下7朵花。我不明白为什么

代码：

public static void emptyVase( int flowersInVase ) {
    if( flowersInVase > 0 ) {
    // take one flower and
        emptyVase( flowersInVase - 1 ) ;

        System.out.println(flowersInVase);


    } else {
           // the vase is empty, nothing to do

    }
}

调用该方法：

public class RecursionPractice {

    public static void main(String[] args) {

        emptyVase(7);    
    }

输出：

1
2
3
4
5
6
7

Answer 1

在递归中，调用的顺序非常重要！当你展开自己的例子时，你可以更好地理解它。它看起来是这样的：

// step 1
// flowerInVase is greater than 7, so the first thing to do is call the function again! 
// Note that the System.out.println is NOT yet reached because of the execution of the function!
// call emptyVse(7 - 1), the *stack* has *remembered* to the current value of *floweInVase* => 7
emptyVase(7); 
// step 2
emptyVase(6);
// condition is *true* yet again, so the same rules as above apply
// current *remembered* value of `floweInVase` is 6
// step 3
emptyVase(5);
// and so on ... until `flowerInVase` is 0 ... now ...

现在堆栈如下所示：

emptyVase(7)
    emptyVase(6)
        emptyVase(5)
            emptyVase(4)
                emptyVase(3)
                    emptyVase(2)
                        emptyVase(1)
                            emptyVase(0) 
                                -> nothing to do, recursion is stopped.
                                -> so go back to previous 
                                -> *stack frame* which is 1
                        System.out.println(1);
                    System.out.println(2);
                System.out.println(3);
            System.out.println(4);
        System.out.println(5);
    System.out.println(6);
System.out.println(7);

在emptyVase(1)的堆栈帧中，函数执行完成，因此打印当前的flowerInVase，即1。回到上一个堆栈帧，每次打印当前存储的变量，直到到达最后一个堆栈帧

这就是为什么顺序是相反的！这也是为什么如果你改变打印和函数执行的顺序，它看起来会和预期的一样

public static void emptyVase( int flowersInVase ) {
    // if there is a flower to take from the vase
    if( flowersInVase > 0 ) {
        // print the count of flowers BEFORE one is taken!
        System.out.println(flowersInVase);
        // take one flower and put it aside
        emptyVase( flowersInVase - 1 ) ;
    } else {
           // the vase is empty, nothing to do
           System.out.println(flowersInVase);
           // print 0!
    }
}

这将产生：

7
6
5
4
3
2
1
0

花瓶实际上是空的，但是因为你的条件是^{，这意味着当最后一次调用是用emptyVase(0)进行的时候，其他部分被取下，你不在那里打印计数器的值。在那里添加一个打印，你会看到一个空花瓶

您理解递归的方法（和示例）很好。我认为在你的例子中需要注意的重要一点是，递归调用会中断当前函数调用并开始一个新的函数调用（再次执行相同的函数），但是上一个调用被记住，一旦新调用完成，流将从中断的地方继续

您可以将每个递归调用想象为一个盒子中的一个盒子的创建：

|-------------------------------|
|--- emptyVase(7)           --- |
|                               |
|   |--- emptyVase(6)       ---||
|   |                          ||
|   |   |--- emptyVase(5)   ---||
|   |   |                      ||
|   |   |   |... and so on     ||
|   |   |   |---emptyVase(0)---||
|   |   |   | S.out.println(0) ||
|   |   |   |------------------||
|   |   |----------------------||
|   |   System.out.println(6)  ||
|   |--------------------------||
|   System.out.println(7);     ||
|-------------------------------|

递归越深入，你拥有的盒子就越多

这也是问题所在。递归在内存分配方面非常昂贵，因为计算机内存有限，如果递归创建了太多的盒子，程序的执行将达到允许的最大盒子数=堆栈帧，并表示堆栈溢出。请注意，我的解释是非常基本的。对于所谓的调用堆栈的详细解释，请看一下这个Wikipedia article - Call stack

Answer 2

Print the flowersInVase before the recursive call. That will solve your confusion like below.

public static void emptyVase( int flowersInVase ) {
          if( flowersInVase > 0 ) {
           // take one flower and


            System.out.println(flowersInVase);  // **** Moved the print Here **********


            emptyVase( flowersInVase - 1 ) ;




          } else {
           // the vase is empty, nothing to do
              System.out.println("Hurray It's empty now..");
          }
        }



public class RecursionPractice {

    public static void main(String[] args) {

        emptyVase(7);
    }

Answer 3

没有。方法很好。它会继续一次从花瓶中取出一朵花，直到花瓶变空。如果您期望以下输出（假设调用方法时flowersInVase为10）：

10 9 8 7 6 5 4 3 2 1

那么你应该写System.out.println(flowersInVase); emptyVase( flowersInVase - 1 );而不是emptyVase( flowersInVase - 1 ); System.out.println(flowersInVase);

Answer 4

改为使用int[]试试（只需复制并粘贴代码，并用数组替换int——您必须验证它是否有效）

public static void emptyVase( int[] flowersInVase ) {
      if( flowersInVase[0] > 0 ) {
       // take one flower and
        emptyVase( flowersInVase[0]-- ) ;

        System.out.println(flowersInVase[0]);

      } 
    }

public class RecursionPractice {

public static void main(String[] args) {

    emptyVase(new int[]{7});

}

它不能与原语int一起使用的原因是，只传递int的值，而不是对保存该值的内存位置的引用，这是在所有方法调用中反映更改所需的

Answer 5

每次对emptyVase()的调用都会打印一个flowersInVase值，所以基本上你会调用System.out.println()7次。第一个打印“1”代表对emptyVase()的最后一个调用，第二个打印“2”代表前一个，依此类推。最后一个“7”是第一次打电话给emptyVase()女巫，她是花瓶里真正的7朵花