为何取模运算能提升Python递归代码的运行速度？

我在解决LeetCode 2466题时，尝试递归解法遇到了超时问题。最初的代码仅在最终结果处取模，考虑到Python没有整数溢出问题，但运行耗时过长；后来修改为在递归函数内每次计算后取模，代码速度立刻恢复正常。我无法理解为何在无整数溢出的Python中，该操作能提升速度，请求解释原因。

初始超时代码 #

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:

        mod = 10**9 + 7

        @lru_cache(None)
        def do(n):
            if n == 0:
                return 1
            elif n < 0:
                return 0
            return do(n-one) + do(n-zero)

        
        return sum(do(x) for x in range(low, high+1))%mod

优化后代码 #

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:

        mod = 10**9 + 7

        @lru_cache(None)
        def do(n):
            # print(f'inside: {n}')
            if n == 0:
                return 1
            elif n < 0:
                return 0
            return (do(n-one) + do(n-zero)) % mod

        
        return sum(do(x) for x in range(low, high+1))%mod

原因解释 #

虽然Python支持任意精度整数，不会出现溢出，但大整数的处理会带来额外的性能开销，具体体现在以下几点：

• 计算开销：大整数的加法运算比小整数慢得多。递归过程中，do(n)的结果会随着n增大呈指数级增长（类似斐波那契数列的增长速度），每次计算大整数的加法都需要更多的CPU周期。提前取模后，所有中间结果都被限制在10^9+7以内，加法运算的效率大幅提升。

• 缓存效率：lru_cache存储的是递归函数的返回值，大整数占用的内存远大于小整数。缓存中存储大量大整数会增加内存占用，同时大整数的哈希计算、缓存的存取操作都会更耗时。取模后每个缓存项都是小整数，缓存的读写速度更快，内存压力也更小。

• 传递开销：大整数在函数调用过程中传递时，需要复制更多的内存数据，相比小整数的传递，这会消耗更多的时间和资源。

简单来说，提前取模的核心作用不是防止溢出，而是通过将所有中间结果限制在一个较小的数值范围内，减少内存占用、加快计算和缓存操作的速度，从而避免超时。

内容的提问来源于stack exchange，提问作者perpetualprime