如何实现可处理奇数长度、不等长输入的Karatsuba乘法

你遇到的无限递归核心原因是子问题规模没有严格小于原问题，且缺失必要的递归终止条件，可按照以下步骤修正实现：

1. 先添加强制递归终止条件 #

在递归函数最开头优先执行以下两个判断，直接返回结果不进入后续拆分逻辑：

• 若输入任意一个数为0，直接返回0
• 若输入任意一个数为个位数（小于10），直接返回两数乘积

2. 修正补零与拆分规则 #

不需要强制将输入补到偶数长度，用数学拆分替代字符串补零操作，避免手动补零带来的拆分错误：

• 计算两个输入的位数，取最大值为n
• 取低位拆分长度m = n // 2
• 用整数运算拆分两个数：
  • a = X // (10 ** m)（X的高位部分）
  • b = X % (10 ** m)（X的低位部分）
  • c = Y // (10 ** m)（Y的高位部分）
  • d = Y % (10 ** m)（Y的低位部分）
    这种拆分方式会自动对齐两个数的位数，且拆分后的每一段长度都严格小于n，子问题规模必然小于原问题，不会出现和原问题等价的递归场景。

3. 可选优化（进一步规避无效递归） #

拆分后如果高位a为0，则ac直接取0不需要递归计算；同理低位b为0时bd直接取0，跳过不必要的递归调用。 #

示例验证（对应你提出的问题输入X=100、Y=14） #

1. 取len_x=3、len_y=2，n = max(3,2)=3，m=3//2=1
2. 拆分得到a=10、b=0、c=1、d=4
3. 三个子问题：ac=10*1、bd=0*4、(a+b)*(c+d)=10*5，所有子问题规模均小于原问题，触发终止条件后可正常返回结果
4. 最终计算：10 * 10^(2*1) + (10*4 + 0*1) * 10^1 + 0 = 1400，和实际乘积一致

你尝试的右侧补零方案本质是将输入先乘10^k，结果再除10^(2k)，虽然整数场景下计算结果正确，但仍需要遵循上述的终止条件和拆分规则，否则仍会出现无限递归问题，优先推荐使用前导对齐的数学拆分方案。
内容的提问来源于stack exchange，提问作者Abdulmalek Almkainzi