递归和返回关键字

Question

我目前正在研究Java教程,现在正在使用Recursions.

我有以下代码来计算传递给阶乘方法的任何数字的阶乘

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;

该函数返回总值(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,但我不知道如何从上面计算出来.

任何解释将不胜感激.

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(); }

它也可能由一个不逻辑循环的函数引起,但由于传递给它的数据而调用自身太多次.例如,递归函数在处理树数据结构时很有用; 如果树太高,它可能会导致堆栈溢出.以下是一些论点,但不会与其他人争论:

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

如果你打电话给possibleStackOverflow(10)你可能很好,但possibleStackOverflow(-1)会抛出异常.

此外,通过VM实现限制,调用possibleStackOverflow(Integer.MAX_VALUE)将抛出StackOverflowException