阶乘末尾非零数字求解代码Java与C耗时差异及优化问询

我实现了一个求解某数阶乘最后非零数字的递归函数，在Java和C语言中使用了完全相同的逻辑代码（如下），但发现两者运行耗时存在明显差异。想请教两个问题：

1. 为什么相同逻辑的代码在两种语言中运行耗时不同？
2. 如何优化这段代码以缩短运行时间？

代码实现 #

// C语言版本
int lastDigitDiffZero(long n) { 
    int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; 
    int i=(int) n; 
    if (n < 10) return dig[i]; 
    if (((n/10)%10)%2 == 0) 
        return (6*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10; 
    else 
        return (4*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10; 
}

// Java语言版本
public class LastNonZeroDigit {
    public static int lastDigitDiffZero(long n) { 
        int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; 
        int i=(int) n; 
        if (n < 10) return dig[i]; 
        if (((n/10)%10)%2 == 0) 
            return (6*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10; 
        else 
            return (4*lastDigitDiffZero(n/5)*dig[(int)n%10]) % 10; 
    }
}

解答 #

1. 为什么相同代码在Java与C中耗时不同？ #

这个差异核心在于两种语言的底层运行机制完全不同，具体来说：

• 编译执行模型：C是纯编译型语言，代码直接被编译成CPU能直接执行的机器码，运行时没有中间层，函数调用、内存操作都是原生硬件级别的，开销极小。而Java是半编译半解释型，代码先转成字节码，运行时依赖JVM（Java虚拟机）来解释或即时编译（JIT）成机器码，JVM还要处理类加载、内存管理、安全校验这些额外工作，哪怕是简单的递归调用，JVM的栈帧处理也比C的原生栈开销大。
• 类型与内存处理：C的基本类型直接对应硬件原生类型，long转int这种操作就是简单的位截断，几乎没开销。但Java的基本类型虽然有对应，但在栈/堆分配、类型转换时会有JVM的额外校验，递归里多次转换的开销会累积起来。
• 递归调用开销：C的递归调用直接用操作系统提供的原生栈，调用和返回就是几个指令的事。Java的递归则要经过JVM的方法调用框架，包括栈帧创建、参数校验、返回值处理等，每一层递归的开销都比C高不少。

另外还有个细节：Java版本里每次递归都会创建一个新的dig数组，这在Java中是堆上分配的操作，还要被GC追踪，而C里的局部数组是在栈上分配的，开销可以忽略，这也是Java耗时更高的一个小原因。

2. 如何优化代码以缩短运行时间？ #

不管是Java还是C，都可以从减少递归开销、优化计算细节这两个方向入手，具体方案如下：

（1）把递归改成迭代实现

递归的最大开销就是函数调用栈，迭代可以彻底避免这部分开销，尤其是当n很大时，迭代的效率提升会很明显。这里是改写后的代码：

// C语言迭代版
int lastDigitDiffZero(long n) {
    static int dig[] = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8}; // 改为静态数组，只初始化一次
    int result = 1;
    while (n > 0) {
        // 提前计算n的十位奇偶性和个位数字，避免重复计算
        long tensDigit = (n / 10) % 10;
        int unitsDigit = (int)(n % 10);
        if (tensDigit % 2 == 0) {
            result = (6 * result * dig[unitsDigit]) % 10;
        } else {
            result = (4 * result * dig[unitsDigit]) % 10;
        }
        n /= 5;
    }
    return result;
}

// Java迭代版
public class LastNonZeroDigit {
    // 把dig改成静态常量，只初始化一次，避免每次调用都创建数组
    private static final int[] DIG = {1, 1, 2, 6, 4, 2, 2, 4, 2, 8};
    
    public static int lastDigitDiffZero(long n) {
        int result = 1;
        while (n > 0) {
            long tensDigit = (n / 10) % 10;
            int unitsDigit = (int)(n % 10);
            if (tensDigit % 2 == 0) {
                result = (6 * result * DIG[unitsDigit]) % 10;
            } else {
                result = (4 * result * DIG[unitsDigit]) % 10;
            }
            n /= 5;
        }
        return result;
    }
}

（2）优化内存与类型细节

• Java端：一定要把dig数组改成静态常量，原代码每次递归都新建数组，这会产生大量不必要的堆分配和GC开销，改成静态后只初始化一次，节省很多资源。另外可以把方法标记为final，帮助JVM更好地做JIT优化。
• C端：把dig改成静态数组，避免每次函数调用都在栈上重新分配数组（虽然栈数组开销小，但静态数组更高效）。同时尽量减少不必要的类型转换，比如直接用(int)(n%10)而不是先转int再取模。

（3）缓存中间结果（针对频繁调用场景）

如果需要多次调用这个函数，可以用哈希表缓存已经计算过的n对应的结果，比如Java用HashMap<Long, Integer>，C用glib的GHashTable或者自己实现简单的缓存，避免重复计算相同的n值，这在频繁调用时能大幅提升效率。

内容的提问来源于stack exchange，提问作者Abhay Mohan Gupta