Karatsuba递归算法陷入无限循环无结果，三值场景失效求助

问题根源 #

你的代码陷入无限循环的核心原因是计算val3时，错误地对字符串执行拼接而非数值相加：

val3 = int(Karatsuba_Recursive((str(A+B)),str((C+D))))

这里的A+B是字符串拼接操作（比如A="12"、B="34"会得到"1234"），而非把A、B当作整数相加得到"46"。这会导致递归调用的参数长度持续增大，永远无法触发len(a) == 1 or len(b) == 1的终止条件，最终陷入无限循环。

另外还存在潜在问题：当A/B/C/D被lstrip("0")处理后变成空字符串时，直接用int(A)会抛出ValueError，需要将空字符串视为0。

修正后的代码 #

def Karatsuba_Recursive(a, b):
    # 处理空字符串输入
    if not a or not b:
        return "0"
    # 终止条件：单个数字直接相乘
    if len(a) == 1 or len(b) == 1:
        return str(int(a)*int(b))
    else:
        m = max(len(a), len(b))
        m2 = m // 2
        # 分割字符串，处理长度不足的情况
        A = a[:-m2] if len(a) > m2 else "0"
        B = a[-m2:].lstrip("0") or "0"
        C = b[:-m2] if len(b) > m2 else "0"
        D = b[-m2:].lstrip("0") or "0"
        
        val1 = int(Karatsuba_Recursive(A, C))
        val2 = int(Karatsuba_Recursive(B, D))
        # 改为数值相加后转字符串
        sum_A_B = str(int(A) + int(B))
        sum_C_D = str(int(C) + int(D))
        val3 = int(Karatsuba_Recursive(sum_A_B, sum_C_D))
        
        return str((val1 * (10 ** (2*m2))) + ((val3 - val1 - val2) * (10 ** m2)) + val2)

关键修改点 #

• 修复数值相加逻辑：将字符串拼接改为整数求和后转字符串，确保递归参数符合算法逻辑。
• 处理空字符串默认值：用or "0"保证空字符串被替换为"0"，避免转整数时报错；分割短字符串时直接设为"0"，简化边界处理。
• 优化切片写法：a[-m2:]等价于原代码的a[-m2:len(a)]，写法更简洁。

测试示例 #

调用Karatsuba_Recursive("1234", "5678")会正确返回"7006652"，与直接计算1234*5678结果一致，且不会陷入循环。

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