递归和Return关键字 （注意：这是一个提问标题，不需要回答）

Question

我目前正在学习Java教程，正在学习递归相关内容。

我有以下代码，可以计算传入factorial方法的任何数字的阶乘：

public class App {
    public static void main(String[] args) {
        //E.g 4! = 4*3*2*1(factorial 4)
        System.out.println(factorial(4));

    }
    private static int factorial(int value){
        //System.out.println(value);
        if (value == 1){
            return 1;
        }
        return factorial(value - 1)*value;
    }
}

我对这部分内容理解有困难

if (value == 1){
    return 1;
}
return factorial(value - 1)*value;

我理解的是return关键字会终止方法并返回与方法声明相同类型（例如int、String等）的值。

当运行以下代码时，会发生什么？

return factorial(value - 1)*value;

该函数返回（值-1）* 值的总和，这将为我提供

(3)*4 = 12
(2)*3 = 6
(1)*2 = 2

随着每次迭代，System.out.println(factorial(4));给出的结果是24。这个数字是如何从方法中得出的呢？由于没有变量来存储值的总和，所以程序将它们存储在哪里呢？另外，我该如何从这些值中得到24呢？

(3)*4
(2)*3
(1)*2

虽然我知道 24 是由 4*3*2*1 求得的，但我不明白如何从上述内容中计算出它。

如果有任何解释，将不胜感激。

- Kenneth .J

Answer 1

你误解了

return factorial(value - 1)*value;

被相乘的值为 factorial(value - 1) 和 value。换句话说，你可以这样重写：

return (factorial(value - 1)) * value;

所以当你通过4时，你会得到这个：

factorial(3) * 4;

等价于

(factorial(2) * 3) * 4;

等价于

((factorial(1) * 2) * 3) * 4;

相当于

1 * 2 * 3 * 4;

如果使用调试器逐步执行代码，您可以轻松地看到其工作方式：

1. 第一次调用函数时传入4。函数评估if，然后调用自身，传入3。（第一次函数调用的状态在堆栈上得以保存，因此当此调用返回时，我们可以从离开的地方继续，现在我们已经有了函数调用的结果。这种“堆栈”抽象实际上不是理解递归所必需的。）

2. 第二次函数调用评估if并调用自身，传入2。

3. 第三次函数调用评估if并调用自身，传入1。
4. 第四次函数调用评估if并返回1。
5. 第三次函数调用继续执行，将刚刚返回的函数的返回值（1）与其参数的值（2）相乘，返回结果（2）。
6. 第二次函数调用继续执行，将刚刚返回的函数的返回值（2）与其参数的值（3）相乘，返回结果（6）。
7. 第一次函数调用继续执行，将刚刚返回的函数的返回值（6）与其参数的值（4）相乘，返回结果（24）。

一些优化编译器会将递归调用转换为循环，但通常无法将递归调用转换为固定表达式，例如 1 * 2 * 3 * 4，因为在编译时通常不知道递归的深度。

如果您按照以下方式修改代码，然后使用调试器逐步执行它，所有这些都将非常清晰：

private static int factorial(int value){
    if (value == 1){
        return 1;
    }
    int recursiveResult = factorial(value - 1);
    return recursiveResult * value;
}

请注意，每次递归调用时，我们都需要在堆栈上存储“挂起”方法的状态，等待调用结果。因此，如果一个方法递归地调用自身（或一系列方法在相互递归中互相调用），堆栈有可能变满。这就是所谓的堆栈溢出。通常情况下，它是由于函数中的错误逻辑导致递归循环引起的：

int stackOverflow() { return stackOverflow(); }

它也可能是由于一个不具有逻辑循环但由于传入的数据而调用自身过多次数的函数引起。例如，递归函数在使用树形数据结构时非常有用；如果树太高，则会导致stackoverflow错误。所以下面的代码也会出现这种错误，对于某些参数会出错，而对于其他参数则不会：

void possibleStackOverflow(int arg) { if (arg == 0) return; possibleStackOverflow(arg - 1); }

如果您调用 possibleStackOverflow(10)，那么很可能没问题，但是调用 possibleStackOverflow(-1) 将抛出异常。

此外，由于虚拟机实现的限制，调用 possibleStackOverflow(Integer.MAX_VALUE) 将抛出 StackOverflowException 异常。

- phoog

---

嗨Phoog，谢谢你的回答。我说的对吗，当我运行factorial（4）时，程序会像你在答案中写的那样不断地扩展/递归运行，直到它达到计数1，然后评估括号中的所有内容（1 * 2 * 3）* 4，得出答案24？ - Kenneth .J

不完全是。它使用堆栈。(编译器在某些情况下可以用循环替换多个堆栈帧，但在这种情况下不会这样做。) 我会在我的答案中添加一点来解释。 - phoog

Answer 2

return factorial(value - 1)*value;

返回value-1乘以value的阶乘。

就像这样：

factorial(4)

= factorial(3) * 4

= factorial(2) * 3 * 4

= factorial(1) * 2 * 3 * 4

= 1 * 2 * 3 * 4 = 24

- mmking

Answer 3

为了理解递归，请尝试绘制调用和参数的树形结构:

factorial(4)  = 4 * factorial(4-1)
                                        |
                                3 * factorial(3-1)
                                               |
                                       2 * factorial(2-1)
                                                      |
                                                      1

尝试使用递归的斐波那契公式。

- user

Answer 4

你的递归方法只有两种结束方式。要么value等于1并返回1，要么它用一个更小的value-1调用自身，并返回那个结果乘以当前的value。

这个方法也可以更详细地写成这样：

private static int factorial(int value){
    if (value == 1){
        return 1;
    }
    int a = factorial(value - 1);
    return a * value;
}

从堆栈的角度来看，它看起来像这样。我插入了虚构的变量a，b和c来指示递归调用返回时的值。

factorial(4)
  |-- a = factorial(4-1=3)
  |    |-- b = factorial(3-1=2)
  |    |    |-- c = factorial(2-1=1)
  |    |    |    +-- return 1          // <-- deepest point in the stack
  |    |    +-- return c * 2 = 2
  |    +-- return b * 3 = 6
  +-- return a * 4 = 24

如果您输入一个更大的起始数字，栈将变得更深，重复调用factorial(value-1)直到最终到达1，然后栈展开以显示答案。如果您输入非常非常大的数字，则会出现堆栈溢出（该网站的名字！），因为您会耗尽内存来保存所需的所有变量。

- Always Learning

Answer 5

你的return语句返回factorial(value-1)*value的结果，每个factorial(value-1)都将被方法调用的结果所替代。

这意味着factorial(4)是：

(factorial(1) * (factorial(2 -1) * (factorial(3 -1) * factorial(4 - 1)))) * 4

这将变成：

(1 * (2 * 3)) * 4，即24。

- Marcos Vasconcelos

---

这不是完全正确的。表达式(factorial(1) * (factorial(2 -1) * (factorial(3 -1) * factorial(4 - 1)))) * 4实际上计算结果为1 * 1 * 2 * 6 * 4，即48。 - phoog

Answer 6

“return”这个词确实会打破当前的方法并返回一个值/结果。然而，在“return”退出之前，您需要评估“return”语句中的“表达式”。例如，“return 1 + 1;”需要在返回之前评估操作符“+”。当您调用“return func(arguments);”时，Java必须在返回之前调用该函数。在这种情况下，它通过这个“调用堆栈”递归地进行（函数调用被放在一个“堆栈”上，最后一个被评估的是第一个）。因此，要真正描述这里发生的事情：

1）“return”语句识别表达式

2）表达式在“堆栈”上调用一个函数

3）堆栈上的函数遇到另一个“return”，需要评估另一个函数

4）...

5）“基本情况”已达成，找到了“1”

6）函数调用沿着堆栈执行以评估表达式

- Gabe Nones

Answer 7

Java使用堆栈来在递归调用之间存储信息。请参阅https://en.wikipedia.org/wiki/Call_stack获取更多信息。

- Transcendence

Answer 8

正如我所想，return f（）;意味着执行f（）并返回f（）的结果。在递归中，return result;只是在递归函数f()之后运行的程序语句。因此，它的执行顺序与模块化递归函数相反。

- Kerwin You