python - Karatsuba 递归错误 : maximum recursion depth exceeded while calling a Python object

Question

我正在尝试在 Python 上实现 Karatsuba 乘法。输入是两个长度为2的幂的整数。它们的长度相同。

def mult(x,y):
    if int(x) < 10 and int(y) <10:
        return int(x)*int(y)
    x_length = len(str(x))//2
    y_length = len(str(y))//2

    a = str(x)[:x_length]
    b = str(x)[x_length:]
    c = str(y)[:y_length]
    d = str(y)[y_length:]

    n = len(a) + len(b)
    m = n//2

    return 10**n* mult(a,c) + 10**m*(mult(a+b, c+d)-mult(a,c)-mult(b,d)) + mult(b,d)

运行多(1234,5678)这会产生以下错误:

if int(x) < 10 and int(y) <10:
RecursionError: maximum recursion depth exceeded while calling a Python object

但是如果我这样做

def mult(x,y):
    if int(x) < 10 and int(y) <10:
        return int(x)*int(y)
    x_length = len(str(x))//2
    y_length = len(str(y))//2

    a = str(x)[:x_length]
    b = str(x)[x_length:]
    c = str(y)[:y_length]
    d = str(y)[y_length:]

    n = len(a) + len(b)
    m = n//2

    return 10**n* mult(a,c) + 10**m*(mult(a,d)+mult(b,c)) + mult(b,d)

所以我在最后一行做了 4 次递归(即 mult(a,c), mult(a,d), mult(b,c), mult(b,d))而不是上面的 3(即 mult(a,c), mult(a+b, c+d), mult(b,d))。

然后结果就ok了。

为什么会这样？我怎样才能只用 3 次递归呢？

Answer 1

a, b, c, d 是字符串。字符串加法是连接。 "1"+ "2" 是 "12"。所以传递给 mult(a+b, c+d) 的不是你想要传递的。

---

长话短说。

首先，递归应该快速终止。让我们看看为什么没有。在mult开头添加print x, y:

def mult(x, y):
    print x, y
    ....

并将输出重定向到一个文件中。结果令人惊讶:

1234 5678
12 56
1 5
12 56
1 5
12 56
1 5
12 56
1 5
....

难怪栈溢出了。问题是，为什么我们要重复 12 56 的情况？让我们添加更多的检测，找出哪个递归调用:

def mult(x,y,k=-1):
    ....
    print a, b, c, d
    ac = mult(a, c, 0)
    bd = mult(b, d, 2)
    return 10**n* ac + 10**m*(mult(a+b, c+d, 1) - ac - bd) + bd

结果是

-1 :  1234 5678
12 34 56 78
0 :  12 56
1 2 5 6 
0 :  1 5
2 :  2 6
1 :  12 56
1 2 5 6 
0 :  1 5
2 :  2 6
1 :  12 56
1 2 5 6 
0 :  1 5
2 :  2 6
1 :  12 56

您可以看到标记为 1 的递归调用总是得到 12 56。这是计算 mult(a + b, c + d) 的调用。那好吧。 a, b, c, d 都是字符串。 "1"+ "2" 是 "12"。不完全是你的意思。

所以，下定决心:参数是整数还是字符串，并相应地对待它们。