Karatsuba Infinite Recursion - Python
<p>Beginner here. I've spent most of the day working on the Karatsuba Algorithm just because I thought it would be fruitful.  I've seen similar questions on here, but they are in other languages and seem strangely complex. The following is my code. The minute it hits the recursive call to ac, it just keeps on recursing.  It's as if it never hits the base case. If anyone could be so kind as to offer some insight as to where things are going wrong, it would be greatly appreciated. For this code, you should assume I'm multiplying 2, base-10, four-digit numbers.</p>

<pre><code>def karatsuba(x, y):
    if len(str(x)) == 1 or len(str(y)) == 1:
        return (x * y)

    else:
        n = (max(len(str(x)), len(str(y))))

        a = x / 10**(n / 2)
        b = x % 10**(n / 2)
        c = y / 10**(n / 2)
        d = y % 10**(n / 2)

        ac = karatsuba(a, c)
        ad = karatsuba(a, d)
        bc = karatsuba(b, c)
        bd = karatsuba(b, d)

        product = (10**n*(ac) + 10**(n/2)*(ad + bc) + bd)

        return product

print (karatsuba(1234, 5678))
</code></pre>

<p>Do you want integer division? In this case, you should use:</p>

<pre><code>a = x // 10 ** (n / 2)
</code></pre>

<p>and</p>

<pre><code>c = y // 10 ** (n / 2)
</code></pre>

<p>Otherwise, your program will be feeding through decimals to your function which I assume is not intended.</p>

<p>I'm also a beginner, feel free to correct me.</p>

python algorithm recursion karatsuba