递归和返回关键字 [英] Recursion and the Return Keyword

问题描述

我目前正在学习Java教程，现在正在使用递归。

I'm currently working my way through the Java tutorials and am currently on Recursions.

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

I have the following code which calculates the factorial of any number passed to the factorial method

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等）。

My understanding is that the return keyword simply terminates the method, and/or returns a value of the same type declared by the method(i.e int,String, etc).

运行以下行时会发生什么？

What happens when the following line is run?

return factorial(value - 1)*value;

该函数返回总值（value - 1）*值，这会给我

the function is returning the total of (value - 1) * value, which would give me

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

每次传递迭代。但是， System.out.println（factorial） （4））; 总共给我 24 。这个数字是如何从这个方法得出的？没有变量来存储值的总和，那么存储它们的程序在哪里？另外，如何从这些值中获得 24 ？

with each passing iteration.However, System.out.println(factorial(4)); gives me a total of 24. How is this number derived from the method? There are no variables to store the sum of the values, so where is the program storing them? Also, how do I get 24 from these values?

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

虽然我知道 24 来自 4 * 3 * 2 * 1 ，但我看不出它是怎么回事从上面计算。

While I know that 24 is derived from 4*3*2*1, I do not see how that can be calculated from the above.

任何解释都将不胜感激。

Any explanation would be greatly appreciated.

推荐答案

你误解了

return factorial(value - 1)*value;

乘以的值是 factorial（value - 1）和值。换句话说，你可以像这样重写它：

The values being multiplied are factorial(value - 1) and value. In other words, you can rewrite it like this:

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

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

So when you pass 4, you get this:

factorial(3) * 4;

相当于

(factorial(2) * 3) * 4;

相当于

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

相当于

1 * 2 * 3 * 4;

如果您使用调试器单步执行代码，可以轻松看到它的工作方式，如下：

The way this works, which you can see easily if you step through the code with a debugger, is as follows:

1. 对函数的第一次调用传递 4 。该函数计算if，然后调用自身，传递 3 。 （第一个函数调用的状态保留在堆栈上，所以当这个调用返回时，我们可以继续我们离开的地方，现在我们有了函数调用的结果。这个堆栈抽象实际上不需要理解递归。）

1. The first call to the function passes 4. The function evaluates the if, then calls itself, passing 3. (The state of the first function call is preserved on the stack, so when this call returns, we can resume where we left off, now that we have the result of the function call. This "stack" abstraction is not actually necessary to understand recursion.)

第二个函数调用计算if并调用自身，传递 2 。

The second function call evaluates the if and calls itself, passing 2.

一些优化编译器将递归调用更改为循环，但通常不可能将递归调用更改为固定表达式，如 1 * 2 * 3 * 4 ，因为在编译时你不要通常不知道递归的深度。

Some optimizing compilers will change recursive calls into loops, but it's not generally possible to change a recursive call to a fixed expression, like 1 * 2 * 3 * 4, because at compile time you don't generally know how deep the recursion will be.

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

All of this will be abundantly clear if you modify your code as follows and then step through it with a debugger:

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

请注意，对于每次递归调用，我们必须存储挂起方法，等待调用的结果，在堆栈上。因此，如果方法以递归方式调用自身（或者一系列方法在相互递归中调用自身），则堆栈有可能变满。这称为堆栈溢出。它通常是由导致递归循环的函数中的错误逻辑引起的：

Note that with each recursive call, we have to store the state of a "suspended" method, waiting for the result of the call, on the stack. For this reason, if a method calls itself recursively (or a chain of methods call themselves in mutual recursion), there is a possibility for the stack to become full. This is known as a stack overflow. It is usually caused by incorrect logic in a function causing a recursive loop:

int stackOverflow() { return stackOverflow(); }

它也可能是由一个没有逻辑循环的函数引起的，但是调用自身太多了时间因为传递给它的数据。例如，递归函数在处理树数据结构时很有用;如果树太高，它可能会导致堆栈溢出。以下是一些参数，但不是其他参数：

It can also be caused by a function that doesn't logically loop, but calls itself too many times because of the data passed to it. For example, recursive functions are useful when working with tree data structures; if the tree is too tall, it can cause a stackoverflow. So will the following, with some arguments, but not with others:

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

如果你打电话给 possibleStackOverflow（10）你很可能，但 possibleStackOverflow（-1）会抛出异常。

If you call possibleStackOverflow(10) you're probably fine, but possibleStackOverflow(-1) will throw an exception.

此外，通过VM实现限制，调用possibleStackOverflow（Integer.MAX_VALUE）将抛出StackOverflowException

Also, by VM implementation limitations, calling possibleStackOverflow(Integer.MAX_VALUE) will throw an StackOverflowException

这篇关于递归和返回关键字的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！