在python类中实现karatsuba递归函数

Question

以前我发了一个关于这个问题的问题，得到了很好的回答。Implementing merge sort function in python class, errors，然而，对于类中的递归，我仍然有一些不理解的地方。在上面的链接问题中，如果我将prefixive self.添加到递归子例程中，就会得到与下面类输出中产生的错误完全相同的错误(本文中的第三个代码块)。我理解为什么会发生这种情况；object.karatsuba()只接受self作为它的输入，但是编码的方法要求2，因此出现了错误。

，请检查下面的代码，然后看到我对第三个代码块之后的解决方案的直觉。

例如:我有一个不想在类中工作的karatsuba乘法的工作实现。标准的课堂乘法在课堂上效果很好，但是.

这是类之外的工作代码：

def zeroPad(numberString, zeros, left = True):
    """Return the string with zeros added to the left or right."""
    for i in range(zeros):
        if left:
            numberString = '0' + numberString
        else:
            numberString = numberString + '0'
    return numberString

def karatsubaMultiplication(x ,y):
    """Multiply two integers using Karatsuba's algorithm."""
    #convert to strings for easy access to digits
    x = str(x)
    y = str(y)
    #base case for recursion
    if len(x) == 1 and len(y) == 1:
        return int(x) * int(y)
    if len(x) < len(y):
        x = zeroPad(x, len(y) - len(x))
    elif len(y) < len(x):
        y = zeroPad(y, len(x) - len(y))
    n = len(x)
    j = n//2
    #for odd digit integers
    if (n % 2) != 0:
        j += 1    
    BZeroPadding = n - j
    AZeroPadding = BZeroPadding * 2
    a = int(x[:j])
    b = int(x[j:])
    c = int(y[:j])
    d = int(y[j:])
    #recursively calculate
    ac = karatsubaMultiplication(a, c)
    bd = karatsubaMultiplication(b, d)
    k = karatsubaMultiplication(a + b, c + d)
    A = int(zeroPad(str(ac), AZeroPadding, False))
    B = int(zeroPad(str(k - ac - bd), BZeroPadding, False))
    return A + B + bd

这是在第39行失败的类中的代码：

class Karatsuba(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def zeroPad(self, numberString, zeros, left = True):
        """Return the string with zeros added to the left or right."""
        for i in range(zeros):
            if left:
                numberString = '0' + numberString
            else:
                numberString = numberString + '0'
        return numberString

    def karatsuba(self):
        """Multiply two integers using Karatsuba's algorithm."""
        #convert to strings for easy access to digits
        self.x = str(self.x)
        self.y = str(self.y)
        #base case for recursion
        if len(self.x) == 1 and len(self.y) == 1:
            return int(self.x) * int(self.y)
        if len(self.x) < len(self.y):
            self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
        elif len(self.y) < len(self.x):
            self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
        n = len(self.x)
        j = n//2
        #for odd digit integers
        if (n % 2) != 0:
            j += 1    
        BZeroPadding = n - j
        AZeroPadding = BZeroPadding * 2
        a = int(self.x[:j])
        b = int(self.x[j:])
        c = int(self.y[:j])
        d = int(self.y[j:])
        #recursively calculate
        ac = self.karatsuba(a, c)
        bd = self.karatsuba(b, d)
        k = self.karatsuba(a + b, c + d)
        A = int(self.zeroPad(str(ac), AZeroPadding, False))
        B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
        return A + B + bd

错误的类版本生成以下输出：

x = 234523546643636
y = 325352354534656

x = Karatsuba(x,y)
x.karatsuba()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-5-aa1c267478ee> in <module>()
      4 x = Karatsuba(x,y)
      5 
----> 6 x.karatsuba()

<ipython-input-1-1d1e9825dcc5> in karatsuba(self)
     37         d = int(self.y[j:])
     38         #recursively calculate
---> 39         ac = self.karatsuba(a, c)
     40         bd = self.karatsuba(b, d)
     41         k = self.karatsuba(a + b, c + d)

TypeError: karatsuba() takes 1 positional argument but 3 were given

我最初的直觉是遵循上面一段所述的解决方案：

class Karatsuba(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def zeroPad(self, numberString, zeros, left = True):
        """Return the string with zeros added to the left or right."""
        for i in range(zeros):
            if left:
                numberString = '0' + numberString
            else:
                numberString = numberString + '0'
        return numberString

    def karatsuba(self):
        """Multiply two integers using Karatsuba's algorithm."""
        #convert to strings for easy access to digits
        self.x = str(self.x)
        self.y = str(self.y)
        #base case for recursion
        if len(self.x) == 1 and len(self.y) == 1:
            return int(self.x) * int(self.y)
        if len(self.x) < len(self.y):
            self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
        elif len(self.y) < len(self.x):
            self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
        n = len(self.x)
        j = n//2
        #for odd digit integers
        if (n % 2) != 0:
            j += 1    
        BZeroPadding = n - j
        AZeroPadding = BZeroPadding * 2
        self.a = int(self.x[:j])
        self.b = int(self.x[j:])
        self.c = int(self.y[:j])
        self.d = int(self.y[j:])
        #recursively calculate
#         ac = self.karatsuba(self.a, self.c)
#         bd = self.karatsuba(self.b, self.d)
        ac = Karatsuba(self.a, self.c)
        ac.karatsuba()
        bd = Karatsuba(self.b, self.d)
        bd.karatsuba()
        k = Karatsuba(self.a + self.b, self.c + self.d)
        k.karatsuba()
#         k = self.karatsuba(self.a + self.b, self.c + self.d)

        A = int(self.zeroPad(str(ac), AZeroPadding, False))
        B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
        return A + B + bd

x = 234523546643636
y = 325352354534656

x = Karatsuba(x,y)
x.karatsuba()

这通过了位置参数错误，但是接下来我有了一个新的问题：

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-34-a862504dede9> in <module>()
     59 
     60 x = Karatsuba(x,y)
---> 61 x.karatsuba()

<ipython-input-34-a862504dede9> in karatsuba(self)
     44 #         bd = self.karatsuba(self.b, self.d)
     45         ac = Karatsuba(self.a, self.c)
---> 46         ac.karatsuba()
     47         bd = Karatsuba(self.b, self.d)
     48         bd.karatsuba()

<ipython-input-34-a862504dede9> in karatsuba(self)
     44 #         bd = self.karatsuba(self.b, self.d)
     45         ac = Karatsuba(self.a, self.c)
---> 46         ac.karatsuba()
     47         bd = Karatsuba(self.b, self.d)
     48         bd.karatsuba()

<ipython-input-34-a862504dede9> in karatsuba(self)
     44 #         bd = self.karatsuba(self.b, self.d)
     45         ac = Karatsuba(self.a, self.c)
---> 46         ac.karatsuba()
     47         bd = Karatsuba(self.b, self.d)
     48         bd.karatsuba()

<ipython-input-34-a862504dede9> in karatsuba(self)
     51 #         k = self.karatsuba(self.a + self.b, self.c + self.d)
     52 
---> 53         A = int(self.zeroPad(str(ac), AZeroPadding, False))
     54         B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
     55         return A + B + bd

ValueError: invalid literal for int() with base 10: '<__main__.Karatsuba object at 0x108142ba8>00'

在这一点上我被困住了。

Answer 1

当我输入这个问题时，我发现自己以一种不同的方式查看我的代码，即思考如何最好地清楚地解释我的问题，以及思考ValueError，然后我发现了这个问题。

在之前的问题中，我正确地遵循了abarnert提供的直觉。问题在于函数的其余部分如何需要递归子程序的值；正如您从ValueError中看到的那样，递归子例程的内存位置正在传递，而不是由子例程生成的值。解决方案很简单:将ac.karatsuba()修改为ac = ac.karatsuba(), etc...和瞧！

--我认为这是一个很好的教程，帮助那些试图理解如何在python中实现递归的人(以及以前链接的问题)。

我希望你同意，给我好的选票！

以下是工人阶级代码：

class Karatsuba(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def zeroPad(self, numberString, zeros, left = True):
        """Return the string with zeros added to the left or right."""
        for i in range(zeros):
            if left:
                numberString = '0' + numberString
            else:
                numberString = numberString + '0'
        return numberString

    def karatsuba(self):
        """Multiply two integers using Karatsuba's algorithm."""
        #convert to strings for easy access to digits
        self.x = str(self.x)
        self.y = str(self.y)
        #base case for recursion
        if len(self.x) == 1 and len(self.y) == 1:
            return int(self.x) * int(self.y)
        if len(self.x) < len(self.y):
            self.x = self.zeroPad(self.x, len(self.y) - len(self.x))
        elif len(self.y) < len(self.x):
            self.y = self.zeroPad(self.y, len(self.x) - len(self.y))
        n = len(self.x)
        j = n//2
        #for odd digit integers
        if (n % 2) != 0:
            j += 1    
        BZeroPadding = n - j
        AZeroPadding = BZeroPadding * 2
        self.a = int(self.x[:j])
        self.b = int(self.x[j:])
        self.c = int(self.y[:j])
        self.d = int(self.y[j:])
        #recursively calculate
#         ac = self.karatsuba(self.a, self.c)
#         bd = self.karatsuba(self.b, self.d)
        ac = Karatsuba(self.a, self.c)
        ac = ac.karatsuba()
        bd = Karatsuba(self.b, self.d)
        bd = bd.karatsuba()
        k = Karatsuba(self.a + self.b, self.c + self.d)
        k = k.karatsuba()
#         k = self.karatsuba(self.a + self.b, self.c + self.d)

        A = int(self.zeroPad(str(ac), AZeroPadding, False))
        B = int(self.zeroPad(str(k - ac - bd), BZeroPadding, False))
        return A + B + bd