为什么这个递归函数不适用于计算零钱到期的硬币数量？

Question

我正在学习用python写递归函数。我写这篇文章是为了解决任何金额的硬币的数量(忽略任何纸币，即25美分是可能的最高面额)。

虽然我知道可能有更好的算法，但现在我只是对为什么我写的这个不起作用感兴趣。如果我输入的不是硬币的确切数量，它会返回一个错误，说递归深度超出了。

import sys
import math



def get_change(m, coin_count):
if m == 0:
return coin_count

else:
if m >= 0.25:
coin_count += math.floor(m / 0.25)
m = m % 0.25

elif m >= 0.1:
coin_count += math.floor(m / 0.1)
m = m % 0.1

elif m >= 0.05:
coin_count += math.floor(m / 0.1)
m = m % 0.05

elif m >= 0.01:
coin_count += math.floor(m / 0.01)
m = m % 0.01

return get_change(m, coin_count)

m = float(input())
coin_count = 0
print(get_change(m, coin_count))

以下是来自有用注释的更正代码。现在工作。决定更改格式，使小数不再是问题:

def get_change(m, coin_count):
if m < 1:
return coin_count
else:
if m >= 25:
coin_count += math.floor(m / 25)
m = m % 25

elif m >= 1:
coin_count += math.floor(m / 10)
m = m %1

elif m >= 5:
coin_count += math.floor(m / 5)
m = m % 5
elif m >= 1:
coin_count += math.floor(m / 1)
m = m % 1
return get_change(m, coin_count)
m = int(input())
coin_count = 0
print(get_change(m, coin_count))

Answer 1

这是修复终止问题的方法(在调用Python对象时导致错误" RecursionError:最大递归深度超出"):

if m < 0.01: # was m == 0

和逻辑错误:

elif m >= 0.05:
coin_count += math.floor(m / 0.05) # was 0.1
m = m % 0.05

下面是修改后的版本，它消除了重复的逻辑，并在返回值中携带计数而不是作为参数:

import sys
import math
def get_change(m):
coins = [0.25, 0.1, 0.05, 0.01]
if m < coins[-1]:
return 0
for coin in coins:
if m >= coin:
count = math.floor(m / coin)
m = m % coin
return get_change(m) + count
m = float(input())
print(get_change(m))

最好以分(即100 * m)为单位进行计算，以便处理整数。