Java递归：示例

发布时间：2020-12-15 04:20:29 所属栏目：Java 来源：网络整理

导读：我知道递归是如何工作的,即：方法调用自己直到它达到基本情况然后它可以开始解决它的问题. 在这个代码示例中是一种方法或从花瓶中移除花朵. 我添加了一个跟踪声明,以便能够看到每次通话后花瓶中有多少花.然而,输出在花瓶中留下7朵花.我很困惑为什么？码：

我知道递归是如何工作的,即：

方法调用自己直到它达到基本情况然后它可以开始解决它的问题.

在这个代码示例中是一种方法或从花瓶中移除花朵.

我添加了一个跟踪声明,以便能够看到每次通话后花瓶中有多少花.然而,输出在花瓶中留下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);    
    }

输出：

解决方法

在递归中,调用的顺序非常重要！当您展开它时,您可以更好地理解您自己的示例.它看起来像这样：

// 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!
    }
}

这将产生：

花瓶实际上是空的,但因为你的条件是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.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!