时间戳

首页 > 解决方案 > 为什么这个递归函数不能用于计算应找零的硬币数量？

python - 为什么这个递归函数不能用于计算应找零的硬币数量？

问题描述

我正在学习用python编写递归函数。我写这篇文章是为了解决在找零时要退回的硬币数量（忽略任何纸币，即四分之一是可能的最高面额）。

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

    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))

标签： pythonrecursion

解决方案

这是您解决终止问题的方法（导致错误“RecursionError：调用 Python 对象时超出最大递归深度”）：

  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）为单位进行计算，以便处理整数。

推荐阅读