java 理解基本递归

understanding basic recursion

提问by sonny

public static void main (String[] args)
{
    System.out.println(factorial(5));
}

public int factorial(int n)
{
    if(n <= 1){
        return 1;
    }
    else{
        return n * factorial(n - 1);
    }
}

I wrote the above directly in here so may not compile but think it does.

我直接在此处写了上面的内容，因此可能无法编译但认为可以。

Can anyone breiefly explain how this works in the sence that how is it stored? It starts off by calculating 5 * (5-1), then down to 4 * (4-1) then 3 * (3-1)..... until it gets to 1 which will just return 1 right? sorry for being so sketchy i would just be interested to find out how this works exactly

任何人都可以简要地解释一下它是如何存储的吗？它从计算 5 * (5-1) 开始，然后下降到 4 * (4-1) 然后是 3 * (3-1)..... 直到它达到 1，它只会返回 1 对吗？抱歉这么粗略，我只是有兴趣了解它是如何工作的

thanks

谢谢

but as it works it out - it gets the values for the individual stages

但随着它的解决 - 它获得了各个阶段的值

5*(5-1) 4 * (4-1) ... ... ...

5*(5-1) 4*(4-1) ... ... ...

how are these stored and then retrieved back or am i missing something?

这些是如何存储然后取回的，还是我遗漏了什么？

回答by Jim Garrison

Imagine you are the computer, and someone hands you a paper with

想象你是电脑，有人递给你一张纸

factorial(3)

written on it. You then execute the procedure, looking at the argument. Since it's > 1, you write

写在上面。然后执行该过程，查看参数。因为它 > 1，所以你写

factorial(2) 

on another piece of paper and "hand it to yourself", waiting until you get the answer to that one before proceeding.

在另一张纸上“把它交给自己”，等到你得到答案后再继续。

Again you execute the procedure. Since 2 is still > 1 you write

再次执行该过程。由于 2 仍然 > 1 你写

factorial(1)

on yet another piece of paper and hand it to yourself, waiting until you get the answer to this one before proceeding.

在另一张纸上递给自己，等到你得到这个问题的答案再继续。

Again, you execute the procedure. This time the input is 1, so you take the first branch and return 1. The invocation that was processing factorial(2) now has an answer so it multiplies 2 by that answer (1) and returns. Now the invocation that was handling factorial(3) gets its answer (2) and multiplies it by 3, giving 6. It then returns that answer to the person who started the whole operation.

再次执行该过程。这次输入为 1，因此您采用第一个分支并返回 1。正在处理 factorial(2) 的调用现在有了一个答案，因此它将 2 乘以该答案 (1) 并返回。现在，处理 factorial(3) 的调用得到它的答案 (2) 并将其乘以 3，得到 6。然后它将该答案返回给启动整个操作的人。

If you imagine that you kept the pieces of paper in a stack in front of you as you were working, that is a visualization of the "stack" in the computer's memory. Each recursive invocation stores the parameter (and any temporary variables) on its own piece of paper (stack frame) literally arranged as a pushdown stack just like the papers, one on top of the other.

如果你想象你在工作时把纸叠成一堆放在你面前，那就是计算机内存中“堆栈”的可视化。每个递归调用将参数（和任何临时变量）存储在它自己的一张纸（堆栈框架）上，就像纸一样按字面排列成一个下推堆栈，一个在另一个之上。

回答by Anthony Forloney

Yes you have it right in the code, it first checks the value of nif it is less than or equal to 1, that is what is referred to as your base case. They are important, they tell your recursive function when to stop.

是的，您在代码中拥有它，它首先检查值n是否小于或等于 1，这就是所谓的base case。它们很重要，它们告诉您的递归函数何时停止。

If the value of nis not less than or equal, it returns the value of nmultiplied by the recursive call of factorialbut with the value n-1up until it reaches it's base case: if (n <= 1)where it returns 1

如果的值n不小于或等于，则返回n乘以递归调用factorial的值，但该值 n-1直到达到它的基本情况：if (n <= 1)它返回的位置1

Your base case was set up by the factorial definiton of 0!and 1!which are both equal to 1.

您的基本情况是由 和 的阶乘定义建立的0!，1!它们都等于 1。

Maybe this diagram might help to understand how the calls work.

也许这张图可能有助于理解调用的工作原理。

5 * fact(5-1) ->
          4 * fact(4-1) ->
                    3 * fact(3-1) ->
                              2 * fact(1) 
                                       1

Which is the same as 5!or 5 x 4 x 3 x 2 x 1

与5!或相同5 x 4 x 3 x 2 x 1

Hope this helps.

希望这可以帮助。

回答by Dan

Are you asking how recursion works internally? The one sentence answer is that every thread has a "call stack" and every time a method is called, a new entry gets pushed onto this stack, which has information about which method is called, and what the arguments were. When the method is finished it places its return value back on the same stack and the calling method pulls it off. So at its height your stack will look like

您是在问递归内部是如何工作的吗？一句话回答是每个线程都有一个“调用堆栈”，每次调用一个方法时，都会将一个新条目推送到这个堆栈上，其中包含有关调用哪个方法以及参数是什么的信息。当该方法完成时，它将其返回值放回到同一个堆栈上，调用方法将其拉出。所以在它的高度，你的堆栈看起来像

factorial (1) called by factorial (2) called by factorial (3) called by factorial (4) called by factorial (5)

阶乘 (1) 被阶乘 (2) 被阶乘 (3) 被阶乘 (4) 被阶乘 (5) 调用

The Wikipedia articleon call stacks seems pretty thorough at first glance.

乍一看，维基百科关于调用堆栈的文章似乎非常详尽。

回答by Jim Barrows

1. In the initial call to factorial, n=5, and is pushed on the stack.
2. Then the else is triggered so 4 is passed to factorial, and is also pushed onto the stack.
3. Then the else is triggered so 3 is passed to factorial, and is also pushed onto the stack.
4. Then the else is triggered so 2 is passed to factorial, and is also pushed onto the stack.
5. Then the else is triggered so 1 is passed to factorial, and is also pushed onto the stack.
6. Then the else is triggered so 0 is passed to factorial, and is also pushed onto the stack.
7. The if gets triggered and 1 is returned to the calling factorial.
8. The if gets triggered and 2 * 1 is returned to the calling factorial.
9. The if gets triggered and 3 * 2 is returned to the calling factorial.
10. The if gets triggered and 4 * 3 is returned to the calling factorial.
11. The if gets triggered and 5 * 4 is returned to the calling factorial.

1. 在对阶乘的初始调用中，n=5，并被压入堆栈。
2. 然后 else 被触发，因此 4 被传递给阶乘，并且也被压入堆栈。
3. 然后 else 被触发，所以 3 被传递给阶乘，并且也被压入堆栈。
4. 然后 else 被触发，因此 2 被传递给阶乘，并且也被压入堆栈。
5. 然后 else 被触发，所以 1 被传递给阶乘，并且也被压入堆栈。
6. 然后 else 被触发，因此 0 被传递给阶乘，并且也被压入堆栈。
7. if 被触发并且 1 返回给调用阶乘。
8. if 被触发并且 2 * 1 返回给调用阶乘。
9. if 被触发并且 3 * 2 返回到调用阶乘。
10. if 被触发并且 4 * 3 返回给调用阶乘。
11. if 被触发并且 5 * 4 返回到调用阶乘。

The stack also gets cleaned up, however that gets too tedious to type. Essentially all values in a method call are pushed onto the stack, and popped off the stack on the methods return. This keeps them separated between recursive calls.

堆栈也会被清理，但是打字太乏味了。本质上，方法调用中的所有值都被压入堆栈，并在方法返回时从堆栈中弹出。这使它们在递归调用之间保持分离。

回答by GrayWizardx

Its important to note that "recursion" works differently in java (a procedural language) than it does in say Haskell or F# (functional languages).

需要注意的是，“递归”在 Java（一种过程语言）中的工作方式与在 Haskell 或 F#（函数式语言）中的工作方式不同。

In Java when we invoke recursion we do so by evaluating the expression tree and resolving each part of it until we determine the value of each part of the expression. If we need to invoke another function we put in a place holder for all intermediate values at that point and then begin to build a new expression tree for the new function.

在 Java 中，当我们调用递归时，我们通过评估表达式树并解析它的每个部分，直到我们确定表达式每个部分的值。如果我们需要调用另一个函数，我们在那个点为所有中间值放置一个占位符，然后开始为新函数构建一个新的表达式树。

In the case of recursion what we are doing is making a call to the same function, hopefully with different terminating values, which needs to be resolved before we can complete the evaluation of the current expression. These expansions are chained together repeatedly until one of two things happens 1) We reach a terminating expression which returns control to the caller (the first part of your if in this case), or we exhaust our ability to place intermediate values in storage and we return an exception (Stack overflow).

在递归的情况下，我们所做的是调用同一个函数，希望使用不同的终止值，这需要在我们完成对当前表达式的评估之前解决。这些扩展被反复链接在一起，直到发生以下两件事之一：1）我们到达一个终止表达式，它将控制权返回给调用者（在这种情况下是 if 的第一部分），或者我们耗尽了将中间值放入存储中的能力，我们返回异常（堆栈溢出）。

In the first case we then begin resolving each of the expression trees from the top of the stack, working our way backwards until their are no stack entries left, at which point the expression tree resolves to the final value returned.

在第一种情况下，我们然后从堆栈顶部开始解析每个表达式树，向后工作直到它们没有堆栈条目，此时表达式树解析为返回的最终值。

Jim's answer is an excellent physical metaphor for this.

对此，吉姆的回答是一个极好的物理比喻。

回答by Matt Baker

It's hard to guess exactly what part of recursion you're having difficulty with, but I'm going to go off this part of your question:

很难准确猜测递归的哪一部分您遇到了困难，但我将离开您的问题的这一部分：

until it gets to 1 which will just return 1 right?

直到它达到 1 才会返回 1 对吗？

I'm guessing you mean, "if it will just return 1, why is the result of the function not1?"

我猜你的意思是，“如果它只返回 1，为什么函数的结果不是1？”

Consider that when you return from a function (in this case, factorial) you are returning a value to whomever originally asked for it.

考虑到当您从函数（在本例中为阶乘）返回时，您正在向最初要求它的任何人返回一个值。

If I say "give me factorial(5)" then factorial(5) will return me a value, but before it can return me the value it has to ask factorial(4) for its value, factorial(5) essentially says "give me factorial(4) so I can multiply it by 5 and give it back to the guy who asked for factorial(5)." Now factorial(4) will return its value to factorial(5) which can multiply it by n and return its value back to me. Recall, Ididn't ask for factorial(4)'s value, I don't even care, and it didn't come back to me, it went back to factorial(5).

如果我说“给我 factorial(5)”，那么 factorial(5) 将返回一个值，但在它返回给我值之前，它必须向 factorial(4) 询问它的值，factorial(5) 本质上是说“给我 factorial(4) 这样我就可以将它乘以 5 并将其还给要求 factorial(5) 的人。” 现在 factorial(4) 将它的值返回给 factorial(5) ，它可以乘以 n 并将它的值返回给我。回想一下，我没有要求阶乘（4）的值，我什至不在乎，它也没有回到我身边，它回到了阶乘（5）。

By the time you hit factorial(1) you'll have factorial(2), factorial(3), factorial(4) and factorial(5) all waiting to get an answer back. Factorial(1) will be return its value (which is 1, because of your base case) to factorial(2), which can finally return to factorial(3) and so on, at which point the recursion will complete and you'll get the value of factorial(5) back.

当您点击 factorial(1) 时，您将有 factorial(2)、factorial(3)、factorial(4) 和 factorial(5) 都在等待得到答案。Factorial(1) 将其值（由于您的基本情况而为 1）返回到 factorial(2)，它最终可以返回到 factorial(3) 等等，此时递归将完成，您将取回 factorial(5) 的值。

回答by Javier

....then 3 * (3-1)..... until it gets to 1 which will just return 1 right?

....then 3 * (3-1)..... 直到达到 1 才返回 1 对吗？

right, but it returns that '1' to the next-to-last invocation, which will multiply by two, returning '2'... to the next-to-next-to-last, which will multiply by three.....

是的，但它将“1”返回到倒数第二次调用，它将乘以 2，将“2”返回到倒数第二次调用，将乘以 3。 ...

回答by Andreas Dolk

A practical approach which requires a good IDE (eclipse, netbeans, IntelliJ):

一种需要良好 IDE（eclipse、netbeans、IntelliJ）的实用方法：

Add a breakpoint to the line which reads return 1and debug the application. When it stops, look at the stack trace. You'll see that the factorial method has been called several times.

在读取return 1和调试应用程序的行中添加断点。当它停止时，查看堆栈跟踪。您会看到阶乘方法已被多次调用。

The eclipse Debug view shows the suspended thread and a stack with six entries, each line representing a line of code where another method is called (except for the top entry - that's the breakpoint). factorial appears five times, you can select each line and see the value of n in the Variable view (this is basic and should work on the other IDE in a similiar way).

Eclipse Debug 视图显示了挂起的线程和一个包含六个条目的堆栈，每行代表一行代码，其中调用了另一个方法（顶部条目除外 - 那是断点）。factorial 出现五次，您可以选择每一行并在 Variable 视图中查看 n 的值（这是基本的，应该以类似的方式在其他 IDE 上工作）。

That should give another idea how recursive method calls work (and why you receive an out of memory error when you do not define the exit criteria properly ;) )

这应该给出另一个想法递归方法调用是如何工作的（以及为什么当您没有正确定义退出标准时会收到内存不足错误；））