Как я могу улучшить мою логику karatsuba, чтобы мой код работал?

Question

Не могу заставить мой алгоритм Карацубы работать должным образом. В моем коде есть бесконечный цикл. Я думаю, что проблема начинается сразу после:

q = str(int(c) + int(d))

потому что нет возвращаемого значения. Почему никто не возвращается?

Мое расследование до сих пор привело меня к выводу, что мой бесконечный цикл:

pq = Karatsuba(p, q)

Повторная настройка моего кода, но пока ничего не получалось.

def Karatsuba( x, y):

    '''
    Input: Two n-digit positive integers. N must be a power of two.

    Output: The product of x and y.
    '''
    if len(x) == 1 and len(y) == 1:

        return int(x) * int(y)

    else:

        split = len(x) // 2

        a = x[:split]
        b = x[split:]
        c = y[:split]
        d = y[split:]

        ac = Karatsuba(a, c)
        bd = Karatsuba(b, d)

        p = str(int(a) + int(b))
        q = str(int(c) + int(d))

        pq = Karatsuba(p, q)

        adbc = pq - ac - bd


        return 10**len(x) * ac + (10**split) * adbc + bd

print(Karatsuba('1234', '5678'))

Ответ должен быть 7006652