Java算法之递归算法计算阶乘

Java算法之递归算法计算阶乘

阶乘是指从1到某个整数n所有整数的乘积。阶乘常用于组合数学，其值巨大，很容易超出标准数据类型的限制。在 Java 编程语言中，可以使用递归算法计算阶乘。下面是该算法的完整攻略。

步骤1：了解递归算法的基本概念

递归算法是指一个函数在执行的过程中调用自身的过程。在递归算法中，每一次的调用都属于某一次的递归调用，每一次调用的返回值都会被上一级的调用所使用。

步骤2：编写计算阶乘的递归算法

使用递归算法计算阶乘的方法非常简单，可以按照如下的基本思路来编写代码：

1. 当输入的整数n等于1时，直接返回1，因为1的阶乘就是1。
2. 当输入的整数n大于1时，将n乘以n-1的阶乘的结果作为当前的阶乘结果。
3. 将计算结果返回。

下面是使用递归算法计算阶乘的Java代码：

public class Factorial {

    public static long factorial(long n) {
        if (n <= 1)
            return 1;
        else
            return n * factorial(n-1);
    }

    public static void main(String[] args) {
        long result = factorial(5);
        System.out.println(result);  // 输出120
    }

}

步骤3：使用递归算法计算其他数的阶乘

可以通过调用该方法来计算其他数的阶乘，例如：

long result = factorial(10);
System.out.println(result);  // 输出3628800

示例说明

下面的两个示例说明可以帮助理解使用递归算法计算阶乘的基本思路。

示例一：计算5的阶乘

1. 调用factorial(5)方法。
2. 判断输入的n是否小于或等于1。由于n等于5，无法通过该判断条件，进入下一步。
3. 计算5*factorial(4)。此时会再次调用factorial方法来计算4的阶乘。
4. 继续判断输入的n是否小于或等于1。由于n等于4，无法通过该判断条件，进入下一步。
5. 计算4*factorial(3)。此时会再次调用factorial方法来计算3的阶乘。
6. 继续判断输入的n是否小于或等于1。由于n等于3，无法通过该判断条件，进入下一步。
7. 计算3*factorial(2)。此时会再次调用factorial方法来计算2的阶乘。
8. 继续判断输入的n是否小于或等于1。由于n等于2，无法通过该判断条件，进入下一步。
9. 计算2*factorial(1)。此时会再次调用factorial方法来计算1的阶乘。
10. 判断输入的n是否小于或等于1。由于n等于1，满足该判断条件，直接返回1。
11. 回到上一层调用，计算2*1=2。
12. 回到上一层调用，计算3*2=6。
13. 回到上一层调用，计算4*6=24。
14. 回到上一层调用，计算5*24=120。
15. 输出120，计算结束。

示例二：计算4的阶乘

1. 调用factorial(4)方法。
2. 判断输入的n是否小于或等于1。由于n等于4，无法通过该判断条件，进入下一步。
3. 计算4*factorial(3)。此时会再次调用factorial方法来计算3的阶乘。
4. 继续判断输入的n是否小于或等于1。由于n等于3，无法通过该判断条件，进入下一步。
5. 计算3*factorial(2)。此时会再次调用factorial方法来计算2的阶乘。
6. 继续判断输入的n是否小于或等于1。由于n等于2，无法通过该判断条件，进入下一步。
7. 计算2*factorial(1)。此时会再次调用factorial方法来计算1的阶乘。
8. 判断输入的n是否小于或等于1。由于n等于1，满足该判断条件，直接返回1。
9. 回到上一层调用，计算2*1=2。
10. 回到上一层调用，计算3*2=6。
11. 回到上一层调用，计算4*6=24。
12. 输出24，计算结束。