你好,我是风一样的树懒,一个工作十多年的后端开发,曾就职京东、阿里等多家互联网头部企业。
接上文,如果你用递归计算 100 的阶乘(100!),可能会发生什么问题?
递归调用会占用函数调用栈,每一次递归调用都会压入栈帧。如果递归深度过大(比如递归到 100),很可能超出栈的大小限制,从而导致栈溢出异常。
在 Java 中,默认的栈深度限制通常在几千到几万之间(根据 JVM 实现和内存分配情况而定),所以计算较小的阶乘可能没有问题,但到 100 时,栈深度可能不够用。
递归方法会增加大量的函数调用开销,而函数调用在计算机中是相对昂贵的操作。对于阶乘这种问题,其实可以通过迭代方法更高效地实现。
阶乘的结果增长非常快。例如:
如果你用 int 或 long 类型来存储结果,很快会超出它们的存储范围:
int 在 Java 中最大值是
long 的最大值是
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"; // 阶乘初始值为 1
for (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));
}
}
今天的内容就分享到这儿,喜欢的朋友可以关注,点赞。有什么不足的地方欢迎留言指出,您的关注是我前进的动力!