100的阶乘，你用递归来做，会有哪些问题？请手动实现改进办法
你好，我是风一样的树懒，一个工作十多年的后端开发，曾就职京东、阿里等多家互联网头部企业。
接上文，如果你用递归计算 100 的阶乘（100!），可能会发生什么问题？
递归调用会占用函数调用栈，每一次递归调用都会压入栈帧。如果递归深度过大（比如递归到 100），很可能超出栈的大小限制，从而导致栈溢出异常。
在 Java 中，默认的栈深度限制通常在几千到几万之间（根据 JVM 实现和内存分配情况而定），所以计算较小的阶乘可能没有问题，但到 100 时，栈深度可能不够用。
递归方法会增加大量的函数调用开销，而函数调用在计算机中是相对昂贵的操作。对于阶乘这种问题，其实可以通过迭代方法更高效地实现。
阶乘的结果增长非常快。例如：
10 ! = 3 , 628 , 800 20 ! = 2 , 432 , 902 , 008 , 176 , 640 , 000 100 ! 9.33262154439441 × 1 0 157
如果你用 int 或 long 类型来存储结果，很快会超出它们的存储范围：
int 在 Java 中最大值是
2 31 − 1 = 2 , 147 , 483 , 647 long 的最大值是
2 63 − 1 = 9 , 223 , 372 , 036 , 854 , 775 , 807
100 的阶乘需要使用 BigInteger 才能处理得了。
import java.math.BigInteger;public class Factorial {public static BigInteger factorial(int n) {if (n == 0 || n == 1) {return BigInteger.ONE; // 0! = 1 and 1! = 1}return BigInteger.valueOf(n).multiply(factorial(n - 1));}public static void main(String[] args) {int n = 100;System.out.println("Factorial of " + n + " is: " + factorial(n));}}
递归问题的本质是可以通过循环解决的，迭代不会产生栈溢出问题，性能也更高：
import java.math.BigInteger;public class Factorial {public static BigInteger factorial(int n) {BigInteger result = BigInteger.ONE;for (int i = 2; i <= n; i++) {result = result.multiply(BigInteger.valueOf(i));}return result;}public static void main(String[] args) {int n = 100;System.out.println("Factorial of " + n + " is: " + factorial(n));}}
核心是重新乘法运算
public class StringFactorial {// 字符串逐位相乘public static String multiply(String num1, int num2) {StringBuilder result = new StringBuilder();int carry = 0; // 进位for (int i = num1.length() - 1; i >= 0; i--) {int digit = num1.charAt(i) - '0'; // 获取当前位数字int product = digit * num2 + carry; // 当前位与num2相乘并加上进位result.append(product % 10); // 保留当前位结果carry = product / 10; // 更新进位}// 最后如果有剩余进位，需要加入结果while (carry > 0) {result.append(carry % 10);carry /= 10;}return result.reverse().toString(); // 翻转字符串得到正确顺序}// 计算 n 的阶乘public static String factorial(int n) {String result = "1"; // 阶乘初始值为 1for (int i = 2; i <= n; i++) {result = multiply(result, i); // 不断累乘}return result;}public static void main(String[] args) {int n = 100; // 计算 100 的阶乘System.out.println("Factorial of " + n + " is:\n" + factorial(n));}}
今天的内容就分享到这儿，喜欢的朋友可以关注，点赞。有什么不足的地方欢迎留言指出，您的关注是我前进的动力！