递归教程

Question

我正在从一本书中学习 Java，并且遇到了有关使用阶乘示例递归的章节。

//A simple example of recursion

package tutorials;

class Factorial {
// this is a recursive method
int fact (int n) {
    int result;

    if(n==1) return 1;
    result = fact(n - 1) * n;
    return result;
  }
}

class Recursion {
    public static void main(String args[]) {
        Factorial f = new Factorial();

        System.out.println("Factorial of 3 is " + f.fact(3));
        System.out.println("Factorial of 4 is " + f.fact(4));
        System.out.println("Factorial of 5 is " + f.fact(5));
    }
}

这段代码给出的结果是"Factorial of 3 is 6"和"Factorial of 4 is 24"

我不明白 class 阶乘中发生了什么，以及为什么不立即计算 *n。这本书没有很好地解释这一点，所以我想我会向任何有经验的程序员寻求帮助。

Answer 1

数字 n 的阶乘定义为： n * (n - 1) * (n - 2) * ... * 1 ，表示将 n 乘以所有小于 n 的正整数。在您的示例中，这是简单的反转，因此您首先计算 n - 1 的阶乘，然后将其乘以 n。继续这个递归，你计算 n - 2、n - 3 的阶乘，依此类推，直到你必须计算 1 的阶乘。在这种情况下，你只需 return 1 本身并返回递归链计算2, 3, ... n - 1, n.

的阶乘

Answer 2

如果您调用 fact(5)，它的工作方式如下：

fact(5)
    5*fact(4)
        4*fact(3)
            3*fact(2)
                2*fact(1)
                    2*1=2 //(since if n==1, 1 is returned directly
                result=2
            result=3*2
        result=4*3*2
    result=5*4*3*2
result=120

递归只是意味着您在自身内部调用一个方法，通常是在操纵参数以适应您的最终结果之后（在本例中为n - 1）。您还要确保定义了终止条件（在本例中为 n==1）。在内部，变量被压入堆栈以便在每次调用时被记住，但这可能是另一天的讨论

递归教程

Recursion Tutorial

java

recursion

factorial