如何递归计算a%b？

Question

我需要编写一个递归函数，它返回两个数字的其余部分。以下是我写的：

def remainder(a,b):
    if a==b:
        return 0
    else:
        k=a-b 
        return a-b + remainder(b,a-k)

如果我们测试remainder(5,3)，函数将返回2并且它是正确的，但是如果我们测试余数(15，3)，我们将得到12和它的false。我只是不知道怎么调试。

Answer 1

您缺少了一个案例：(当a

def remainder(a,b):
    if a<b: #trivial: remainder = a - b*0 = a
        return a
    else: #reduce the problem to a simple one
        return remainder(a-b, b)

测试：

print remainder(15,3)

输出：

0

在这里，如果您很懒并且不想写超过2行的话：

def remainder(a,b):
    return a if a < b else remainder(a-b, b)

Answer 2

应该是这样的：

def remainder(a,b):
if a<b:
    return a
else:
    return remainder(a-b,b)

Answer 3

你可以：

def remainder(a, b):
    if a < b:
        return a
    return remainder(a - b, b)

示例：

>>> remainder(15, 3)
0
>>> remainder(14, 3)
2
>>> remainder(13, 3)
1

如果是a < b，那就意味着我们完成了:我们知道计算的结果，我们可以返回a。否则，我们需要从b中减去a，然后再递归地调用remainder。然后，这种情况可以反复进行，直到a小于b为止。一旦发生这种情况，递归就停止了(也就是说，它不会再次调用remainder )，但是我们能够返回结果。