俄罗斯农民乘法 Python 使用递归尾

Question

我尝试编写此代码并运行它，但结果显示 "None"。我通过在循环函数中添加另一个 else 进行了编辑，然后它实际上产生了一个 int 结果 '57' 这不完全是答案。

def double(n):

    return n*2

def halve(n):

    return n//2

def mult(m,n):

    def loop(m,n):

            if n>1:
                if n%2 != 0:
                    return m + loop(double(m),halve(n))
                else:
                    return m #added another else
            else:
                return m

    if n>0:
            return loop(m,n)
    else:
            return 0

print(mult(57,86))

Answer 1

通过简单递归

def double(n):
    return n * 2

def halve(n):
    return n // 2

def mult(m, n, a = 0):
    if n % 2 != 0:
        a = a + m
        m = double(m)
        n = halve(n)
    if n % 2 == 0:
        m = double(m)
        n = halve(n)
    if n != 0:
        return mult(m, n, a)
    return a

print(mult(57, 86))

通过嵌套函数

def double(n):
    return n * 2

def halve(n):
    return n // 2

def mult(m, n):

    def loop(m, n, a = 0):

        if n % 2 != 0:
            a = a + m
            m = double(m)
            n = halve(n)
        if n % 2 == 0:
            m = double(m)
            n = halve(n)
        if n != 0:
            return loop(m, n, a)
        return a
    return loop(m, n)

print(mult(57, 86))

俄罗斯农民乘法 Python 使用递归尾

Russian Peasant Multiplication Python using recursive-tail

python

recursion

multiplication