Java 递归 : Example

Question

我知道如何 recursion有效，即:

方法会调用自身，直到达到基本情况，然后才能开始解决问题。

在此代码示例中是一种从花瓶中取出花朵的方法。

我添加了一个跟踪语句，以便能够在每次调用后查看花瓶中有多少花。然而，输出在花瓶中留下了 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

花瓶其实是空的，但是因为你的条件是flowerInVase > 0 ，这意味着当最后一次调用时使用emptyVase(0) else 部分被占用，您不在那里打印计数器的值。在那里添加一张打印品，您将看到一个空花瓶。

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

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

|-------------------------------|
|--- 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 .