Python 递归难题：用6、9和20个装购买n个麦克鸡块

Question

我注意到有一些和这个问题相关的问题（我在网上也查了一下这个问题）。不过，它们都是用循环的方法来解决的；我有点困惑，不知道这个问题怎么用递归来解决：

def is_buyable(n):
''' return whether amount n McNuggets is buyable at McDonalds (using 6, 9 and 20 packs) '''
    if n == 0:
        return True

    #...
    #insert some code or if statement, with call on is_buyable(n)

    else:
        return False

正如你所看到的，这个方法返回的是一个布尔值（也就是对或错）。任何帮助都非常感谢！

Answer 1

def is_buyable(n):
    ''' return whether amount n McNuggets is buyable at McDonalds (using 6, 9 and 20 packs) '''
    if n == 0:
        return True
    for i in (6, 9, 20):
        if n >= i and is_buyable(n - i):
            return True
    return False

编辑: 使用递归意味着这个函数会自己调用自己，来解决原问题的一个小问题。在这个例子中，函数会检查以下三个数量中是否至少有一个是可以购买的（即True）：

• 初始数量减去6（买了一包6个的）
• 初始数量减去9（买了一包9个的）
• 初始数量减去20（买了一包20个的）

如果这三个修改后的数量中至少有一个是可以购买的，那么当前的数量（n）也可以购买。

这个函数还会检查我们最开始拥有的数量（n）是否大于或等于我们想要从中减去的包的数量，所以会有n >= i这个检查。

Answer 2

这可能不太符合你的作业模板，不过：

def is_buyable(n):
    return n==0 or any(n >= i and is_buyable(n - i) for i in (6,9,20))

Answer 3

递归的工作原理是把每个问题分解成一个“更小”的同类问题。在这种情况下，你可以插入这段代码：

elif n < 0:
    return False

elif is_buyable(n - 20) or is_buyable(n - 9) or is_buyable(n - 6):
    return True