Python递归计算区间整除数报Maximum recursion depth exceeded修复

你当前实现的递归函数每次递归仅将start参数加1，递归深度完全等于区间跨度值。Python默认的最大递归深度阈值仅为1000左右，当区间跨度达到1e12级别时，必然触发Maximum recursion depth exceeded错误。除此之外，这种逐一枚举每个数字判断的逻辑时间复杂度为O(end-start)，面对1e12级别的区间哪怕不触发递归深度错误，也需要极长时间才能跑完，完全不具备实用性。

不需要逐一枚举数字，直接用整数除法做数学计算即可，时间复杂度O(1)，瞬间得到结果，完全不存在递归深度问题：

闭区间[start, end]内可被n整除的数字总数 = 0到end区间内可被n整除的数字个数 减去 0到start-1区间内可被n整除的数字个数，公式为 end // n - (start - 1) // n

对应实现代码：

def count(start, end, n):
    return end // n - (start - 1) // n


start = 1
end = 10**12 - 1
n = 5
print(count(start, end, n))

运行上述代码会瞬间输出结果199999999999，和逐一枚举的计算结果完全一致。

如果你出于练习目的必须保留递归写法，需要修改递归步进逻辑，不要每次仅给start加1，而是直接跳到下一个符合整除条件的数。需要注意Python本身不支持尾递归优化，当n取值极小（比如n=1）时，递归深度依然会超过阈值，实用性远不如上面的数学计算方案。递归修改参考：

def count(start, end, n):
    # 定位第一个落在区间内的可被n整除的数
    first = start if start % n == 0 else start + (n - start % n)
    if first > end:
        return 0
    # 剩余区间的计数加当前1个
    return 1 + count(first + n, end, n)

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