Python实现Karatsuba算法触发RecursionError递归错误的原因是什么

• 0值分支返回值非法：a == 0 or b == 0的判断分支里直接返回了None，后续递归调用传入None后，数值运算、长度判断逻辑都会全部异常，该分支应该返回0。
• 除法逻辑错误导致无限递归：Python3中/是浮点除法，你计算m = n/2、拆分x = a/pow(10, m)得到的都是浮点值，比如n=7时m=3.5，pow(10, 3.5)是约3162.277的浮点数，拆分出来的x、y、w、z都是带小数的浮点值，每次计算len(str(浮点值))会包含小数点、小数位，长度永远无法降到你设定的阈值4以下，递归会无限向下触发，最终导致RecursionError。正确做法是使用整数运算，m取整数，拆分用整数除法//。
• Karatsuba公式参数写错：你计算r的时候传参为prod2(x+y, w+x)，标准Karatsuba算法中r应该是(x+y)*(w+z)，第二个参数错误会导致计算结果不符合预期。

修正后可运行代码 #

threshold = 4

def prod2(a, b):
    if a == 0 or b == 0:
        return 0
    n = max(len(str(a)), len(str(b)))
    if n <= threshold:
        return a * b
    m = n // 2
    base = pow(10, m)
    x = a // base
    y = a % base
    w = b // base
    z = b % base
    r = prod2(x + y, w + z)
    p = prod2(x, w)
    q = prod2(y, z)
    return p * pow(10, 2 * m) + (r - p - q) * pow(10, m) + q

a = 12314124
b = 123123
print(prod2(a, b))
# 输出结果为1516105260852，和直接计算a*b结果一致

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