100的阶乘,你用递归来做,会有哪些问题?请手动实现改进办法

你好,我是风一样的树懒,一个工作十多年的后端开发,曾就职京东、阿里等多家互联网头部企业。

点击下方👇关注公众号,带你一起复习后端技术,看看面试考点,补充积累技术知识,每天都为面试准备积累


接上文,如果你用递归计算 100 的阶乘(100!),可能会发生什么问题?


01
栈溢出问题(StackOverflowError)


递归调用会占用函数调用栈,每一次递归调用都会压入栈帧。如果递归深度过大(比如递归到 100),很可能超出栈的大小限制,从而导致栈溢出异常。

在 Java 中,默认的栈深度限制通常在几千到几万之间(根据 JVM 实现和内存分配情况而定),所以计算较小的阶乘可能没有问题,但到 100 时,栈深度可能不够用。


02
性能问题


递归方法会增加大量的函数调用开销,而函数调用在计算机中是相对昂贵的操作。对于阶乘这种问题,其实可以通过迭代方法更高效地实现。


03
溢出问题(仅针对较小的数据类型)


阶乘的结果增长非常快。例如:

  • 10!=3,628,80010! = 3,628,80010!=3,628,800

  • 20!=2,432,902,008,176,640,00020! = 2,432,902,008,176,640,00020!=2,432,902,008,176,640,000

  • 100!100!100! 的值大约是 9.33262154439441×101579.33262154439441 \times 10^{157}9.33262154439441×10157

如果你用 int 或 long 类型来存储结果,很快会超出它们的存储范围:

  • int 在 Java 中最大值是 2311=2,147,483,6472^{31} - 1 = 2,147,483,647231−1=2,147,483,647

  • long 的最大值是 2631=9,223,372,036,854,775,8072^{63} - 1 = 9,223,372,036,854,775,807263−1=9,223,372,036,854,775,807

100 的阶乘需要使用 BigInteger 才能处理得了。


04
递归实现示例(Java):


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


05
改进方法:用迭代代替递归


递归问题的本质是可以通过循环解决的,迭代不会产生栈溢出问题,性能也更高:

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


06
面试Coding:请使用String的方式实现


核心是重新乘法运算

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


今天的内容就分享到这儿,喜欢的朋友可以关注,点赞。有什么不足的地方欢迎留言指出,您的关注是我前进的动力!

END


扫码关注

一起积累后端知识
不积跬步,无以至千里
不积小流,无以成江海

喜欢此内容的人还喜欢

谈谈id那些事(五)——美团的 Leaf 的ID生成


一个阿里二面面试官必问的问题


Lambda表达式说爱你不容易


分享面试:mysql数据库索引失效的情况


Spring-Boot中一个不起眼的好工具StopWatch