cs61a中的递归小例子

在学习cs61a的过程中，学习到一个题目有关递归使用的，分享一下

题目：

Q3: Count Dollars

Given a positive integer total, a set of dollar bills makes change for total if the sum of the values of the dollar bills is total. Here we will use standard US dollar bill values: 1, 5, 10, 20, 50, and 100. For example, the following sets make change for 15:

• 15 1-dollar bills
• 10 1-dollar, 1 5-dollar bills
• 5 1-dollar, 2 5-dollar bills
• 5 1-dollar, 1 10-dollar bills
• 3 5-dollar bills
• 1 5-dollar, 1 10-dollar bills

Thus, there are 6 ways to make change for 15. Write a recursive function count_dollars that takes a positive integer total and returns the number of ways to make change for total using 1, 5, 10, 20, 50, and 100 dollar bills.

Use next_smaller_dollar in your solution: next_smaller_dollar will return the next smaller dollar bill value from the input (e.g. next_smaller_dollar(5) is 1). The function will return None if the next dollar bill value does not exist.

Important: Use recursion; the tests will fail if you use loops.

Hint: Refer to the implementation of count_partitions for an example of how to count the ways to sum up to a final value with smaller parts. If you need to keep track of more than one value across recursive calls, consider writing a helper function.

def next_smaller_dollar(bill):"""Returns the next smaller bill in order."""if bill == 100:return 50if bill == 50:return 20if bill == 20:return 10elif bill == 10:return 5elif bill == 5:return 1def count_dollars(total):"""Return the number of ways to make change.>>> count_dollars(15)  # 15 $1 bills, 10 $1 & 1 $5 bills, ... 1 $5 & 1 $10 bills6>>> count_dollars(10)  # 10 $1 bills, 5 $1 & 1 $5 bills, 2 $5 bills, 10 $1 bills4>>> count_dollars(20)  # 20 $1 bills, 15 $1 & $5 bills, ... 1 $20 bill10>>> count_dollars(45)  # How many ways to make change for 45 dollars?44>>> count_dollars(100) # How many ways to make change for 100 dollars?344>>> count_dollars(200) # How many ways to make change for 200 dollars?3274>>> from construct_check import check>>> # ban iteration>>> check(SOURCE_FILE, 'count_dollars', ['While', 'For'])True""""*** YOUR CODE HERE ***"

这道题大致就是个找零钱的问题，区别是不是那种贪心算法说的怎么找零钱花的步骤最少，这个题目是要把每种找零钱的方法数量统计出来。

用到递归

理解递归最重要的一点是，你要相信你正在写的这个函数已经能够解决规模更小的问题。

想象一下，你是一个项目经理，你的任务是计算 count_helper(15, 10)，也就是“用10及以下的面值凑成15的方法数”。你很忙，不想自己做，于是你雇了两个实习生。

你对两个实习生下达指令：

1. 你对实习生A说：“你去计算一下‘用10及以下面值凑成5的方法数’。因为我已经决定用一张10的钞票了，所以你们只需要解决剩下的5就行。” 这就是 count_helper(15 - 10, 10)。

2. 你对实习生B说：“我决定不用10的钞票了。你去计算一下‘用5及以下面值凑成$15的方法数’。” 这就是 count_helper(15, 5)。

你不需要关心这两个实习生是怎么算的，你只需要相信他们会给你正确的结果。一旦他们俩都回来告诉你结果（比如实习生A说有2种，实习生B说有4种），你的工作就非常简单：把两个结果加起来（2+4=6），然后向上级汇报。

这，就是递归的本质。每个函数调用都像一个项目经理，它把工作分解，交给“下一级”的函数调用去处理。

---

代码分步详解

我们来逐行分析代码，看看它是如何实现上面那个故事的。

1. 外层函数 count_dollars(total)

Python

def count_dollars(total):# ...# 启动递归return count_helper(total, 100)

这个函数非常简单，它就像是公司的 CEO。他接到一个大任务（“凑够 total 元！”），但他不亲自干活。他直接把任务交给了最有能力的总监 count_helper，并告诉他：“目标金额是 total，你可以动用公司里最大面值的资源（$100）。”

它的作用就是初始化整个递归流程。

2. 内层核心函数 count_helper(amount_left, largest_bill)

这是真正干活的函数，我们把它拆成两部分来看：终止条件和递归分解。

a) 终止条件 (Base Cases)

递归不能无限进行下去，必须有终点。这些终点就是我们能直接知道答案的、最简单的情况。

Python

# 终止条件 1: 完美的成功
if amount_left == 0:return 1

• 含义：当剩余金额 amount_left 正好是 0 时，说明我们不多不少，正好凑齐了目标。

• 为什么返回 1？ 因为这代表我们已经成功找到了一条完整的、有效的组合路径。这个 1 会被返回给上一级的调用，作为其计算结果的一部分。它代表“嘿，我这里找到 1 种方法！”。

Python

# 终止条件 2: 彻底的失败
if amount_left < 0 or largest_bill is None:return 0

• 含义：这条路走不通了。有两种失败可能：

  1. amount_left < 0：我们用的上一张钞票面值太大了，导致总额超了（比如目标是5，但我们用了10）。

  2. largest_bill is None：我们已经把所有面值的钞票都试过了（连$1都不能用了），但 amount_left 仍然大于0。钱不够，凑不齐了。

• 为什么返回 0？ 因为这条探索路径是死胡同，它对最终的总方法数没有任何贡献。它向上级汇报：“我这里找到 0 种方法。”

b) 递归分解 (Recursive Step)

如果程序没有在终止条件处退出，说明问题还不够简单，需要继续分解。

Python

# 方法1: 用了 largest_bill (实习生A的工作)
with_largest_bill = count_helper(amount_left - largest_bill, largest_bill)

• 逻辑：我们决定“使用”当前这张 largest_bill。

• 参数变化：

  • amount_left - largest_bill：因为用了一张，所以需要凑的金额减少了。

  • largest_bill：保持不变。这一点很关键！因为我们用了这张钞票后，仍然可以继续使用同样面值的钞票（比如凑10，可以用两个5）。

Python

# 方法2: 没用 largest_bill (实习生B的工作)
without_largest_bill = count_helper(amount_left, next_smaller_dollar(largest_bill))

• 逻辑：我们决定“不使用”当前这张 largest_bill，把它彻底排除。

• 参数变化：

  • amount_left：保持不变。因为没用这张钞票，所以目标金额一点没少。

  • next_smaller_dollar(largest_bill)：我们承诺了不用 largest_bill，所以只能从下一个更小面值的钞票里想办法了。

Python

return with_largest_bill + without_largest_bill

• 含义：作为“项目经理”，我们现在收到了两个实习生的报告结果。我们把它们加起来，就是当前这个问题的最终答案，然后把这个答案再返回给自己的上级。

走一个简单的例子：count_dollars(6)

1. count_dollars(6) 调用 helper(6, 100)。

2. helper(6, 100) 分解成 helper(-94, 100) (返回0) + helper(6, 50)。结果是 helper(6, 50) 的结果。

3. ... 这个过程一直持续，直到调用 helper(6, 5)。

4. helper(6, 5) 这是关键的一步：

   • 用 $5: 调用 helper(6 - 5, 5)，也就是 helper(1, 5)。

   • 不用 $5: 调用 helper(6, 1)。

5. 现在我们有两个分支需要解决：

   • 分支A: helper(1, 5)

     • 用 5: helper(-4, 5) -> 返回 0。

     • 不用 5: helper(1, 1)。

       • helper(1, 1) 又分解成：

         • 用 1: helper(0, 1) -> 返回 1 (成功找到组合：$5 + $1)。

         • 不用 1: helper(1, None) -> 返回 0。

       • 所以 helper(1, 1) 返回 1+0 = 1。

     • 因此，分支A helper(1, 5) 最终返回 0 + 1 = 1。

   • 分支B: helper(6, 1)

     • 用 1: helper(5, 1)。

     • 不用 1: helper(6, None) -> 返回 0。

     • helper(5, 1) 会一路递归下去，最终调用 helper(0, 1)，返回 1 (成功找到组合：6个$1)。

     • 因此，分支B helper(6, 1) 最终返回 1 + 0 = 1。

6. 回到第4步，helper(6, 5) 收到两个分支的结果：分支A返回 1，分支B返回 1。

7. helper(6, 5) 将它们相加，返回 1 + 1 = 2。

最终，count_dollars(6) 得到结果 2。这两种方法就是 (一个5+一个1) 和 (六个$1)。