Java 递归：示例
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/23932519/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Java Recursion: Example
提问by
I am aware of how recursionworks, i.e:
我知道递归是如何工作的，即：
method calls itself until it reaches a base case then it can start solving its problem.
method calls itself until it reaches a base case then it can start solving its problem.
In this code example is a method or removing flowers from a vase.
在此代码示例中是一种方法或从花瓶中取出鲜花。
I have added a trace statement to be able to see how many flowers are in the vase after every call. However the output leaves 7 flowers in the vase. I am confused as to why?
我添加了一个跟踪语句，以便能够在每次调用后查看花瓶中有多少朵花。然而，输出在花瓶中留下了 7 朵花。我很困惑为什么？
Code:
代码：
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
}
}
Invoking the method:
调用方法：
public class RecursionPractice {
public static void main(String[] args) {
emptyVase(7);
}
Output:
输出：
1
2
3
4
5
6
7
回答by Mifmif
Each call to emptyVase()will print a flowersInVasevalue , so basicly you will call System.out.println()7 times. The first print '1' is for the last call to emptyVase(), the second one '2' is for the before last one and so again .The last one '7' is for the first call to emptyVase()witch was realy 7 flower in the vase.
每次调用emptyVase()都会打印一个flowersInVasevalue ，所以基本上你会调用System.out.println()7 次。第一个打印 '1' 代表最后一次调用emptyVase()，第二个打印 ' 2' 代表前最后一个，依此类推。最后一个打印 ' 7' 代表第一次调用emptyVase()女巫是花瓶里的 7 朵花。
回答by Yasin
Nopes. The method is fine. It will keep on removing one flower at a time from the vase till the vase is empty. If you are expecting the below output(assuming that the method is called with flowersInVaseto be 10 ):
不。方法没问题。它将不断从花瓶中一次取出一朵花，直到花瓶为空。如果您期待以下输出（假设该方法被调用flowersInVase为 10 ）：
10
9
8
7
6
5
4
3
2
1
10
9
8
7
6
5
4
3
2
1
Then you should write System.out.println(flowersInVase); emptyVase( flowersInVase - 1 );instead of emptyVase( flowersInVase - 1 ); System.out.println(flowersInVase);
那么你应该写System.out.println(flowersInVase); emptyVase( flowersInVase - 1 );而不是emptyVase( flowersInVase - 1 ); System.out.println(flowersInVase);
回答by MadConan
try it with an int[] instead (only copy and pasted your code and substituted the array for the int -- you'll have to verify it works)
尝试使用 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});
}
The reason it won't work with a primitive intis because only the valueof the int is passed, not a reference to the memory location holding the value, which is what you need to have in order to have the change reflected in all method invocations.
它不适用于原语int的原因是因为只传递了 int的值，而不是对保存该值的内存位置的引用，这是为了在所有方法调用中反映更改所需要的.
回答by Munesh
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);
}
回答by pasty
In recursion the order of the calls is very important! You can understand better your own example when you unrollit. It will look like this:
在递归中，调用的顺序非常重要！当你展开它时，你可以更好地理解你自己的例子。它看起来像这样：
// 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 ...
Now the stacklooks like this:
现在堆栈看起来像这样：
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);
In stack framefor emptyVase(1)the function execution is done, so print the current flowerInVasewhich is 1. Go back to the previous stack frame, every time print the currently stored variableuntil the last stack frameis reached.
在函数执行的堆栈帧中emptyVase(1)完成，因此打印当前flowerInVase为1。回到上一个栈帧，每次打印当前存储的变量，直到到达最后一个栈帧。
And that is why the order is reverse! That is also why if you change the order of the print and the function execution it will look as expected.
这就是为什么顺序是相反的！这也是为什么如果您更改打印和函数执行的顺序，它将看起来像预期的那样。
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!
}
}
This will produce:
这将产生：
7
6
5
4
3
2
1
0
The vaseis actually empty, but because your condition is flowerInVase > 0, this means when the last callis made with emptyVase(0)the elsepart is taken and you don't print there the value of the counter. Add a print there and you will see an empty vase.
该花瓶其实是空的，但因为你的条件是flowerInVase > 0，当最后这种方式调用与制作emptyVase(0)的其他取一部分，你不打印那里的计数器的值。在那里添加印刷品，您将看到一个空花瓶。
Your approach (and the example) for understanding recursion is good. I think the important thing to notice in your example is the fact, that the recursive call interruptsthe current function call and starts a new one (executes the same function again), but the previous call is rememberedand once the new call is done, the flowcontinues from where it was interrupted!
您理解递归的方法（和示例）很好。我认为在您的示例中要注意的重要一点是，递归调用会中断当前函数调用并启动一个新函数调用（再次执行相同的函数），但是会记住上一次调用，并且一旦新调用完成，该流程从被中断的地方继续！
You could imagine every recursive callas a creation of a box in a box:
你可以把每一次递归调用想象成在一个盒子中创建一个盒子：
|-------------------------------|
|--- emptyVase(7) --- |
| |
| |--- emptyVase(6) ---||
| | ||
| | |--- emptyVase(5) ---||
| | | ||
| | | |... and so on ||
| | | |---emptyVase(0)---||
| | | | S.out.println(0) ||
| | | |------------------||
| | |----------------------||
| | System.out.println(6) ||
| |--------------------------||
| System.out.println(7); ||
|-------------------------------|
The deeperthe recursion, the more boxes you have.
在更深的递归，你有更多的箱子。
This is also where the problem is. Recursion is pretty expensive in terms of memory allocation and because the computers have a finite amount of memory, if the recursion creates too manyboxes, the execution of the program reaches the maximum allowed count of boxes = stack framesand says stack overflow. Be aware that my explanation is a very basic one. For a thorough explanation of the so called call stackhave a look at this Wikipedia article - Call stack.
这也是问题所在。递归在内存分配方面非常昂贵，并且因为计算机的内存量是有限的，如果递归创建太多框，程序的执行将达到最大允许的框数 = 堆栈帧并表示堆栈溢出。请注意，我的解释是一个非常基本的解释。有关所谓的调用堆栈的详细解释，请查看这篇维基百科文章 - 调用堆栈。
