java - 递归教程

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

这段代码给出的结果是“3 的阶乘是 6”和“4 的阶乘是 24”

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

Answer 1

如果您调用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)。在内部，变量被推送到堆栈上以便每次调用时都被记住，但这可能是另一天的讨论