python - 解决 RecursionError：获取对象的 str 时超出最大递归深度

Question

我没有明白我的代码有什么问题。我应该如何解决 Karatsuba 乘法中的递归错误？

def karatsuba(x,y):
    if len(str(x))==1 or len(str(y))==1:
        return int(x)*int(y)
    else:
        n=max(len(str(x)),len(str(y)))
        nby2=n//2
        a=x/(10**nby2)
        b=x%(10**nby2)
        c=y/(10**nby2)
        d=y%(10**nby2)
        ac=karatsuba(a,c)
        bd=karatsuba(b,d)
        k=karatsuba(a+b,c+d)-ac-bd
        p=((10**2*nby2)*ac+((10**(nby2))*k)+bd)
        return p

错误信息 -

line 11, in karatsuba
    ac=karatsuba(a,c)
  [Previous line repeated 989 more times]

 line 2, in karatsuba
    if len(str(x))==1 or len(str(y))==1:
RecursionError: maximum recursion depth exceeded while getting the str of an object

Answer 1

x/(10**nby2)返回 float 所以它必须是x//(10**nby2). 也(10**2*nby2)改成(10**(2*nby2)

def karatsuba(x,y):
    if len(str(x))==1 or len(str(y))==1:
        return int(x)*int(y)
    else:
        n=max(len(str(x)),len(str(y)))
        nby2=n//2
        a=x//(10**nby2)
        b=x%(10**nby2)
        c=y//(10**nby2)
        d=y%(10**nby2)
        ac=karatsuba(a,c)
        bd=karatsuba(b,d)
        k=karatsuba(a+b,c+d)-ac-bd
        p=((10**(2*nby2))*ac+((10**(nby2))*k)+bd)
        return p