Как вычислить% 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 и его ложь. Я просто не знаю, как его отладить.

Answer 1

Вы пропускаете случай: (когда < б)

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), но мы можем вернуть результат.