Python函数中None使用场景疑问:CS61A硬币找零递归异常排查
问题核心bug定位
你的代码算不对100面值场景的原因,和size == None的判断写法关系不大,本质是三个递归逻辑硬伤:
- 递归分支的扣减对象完全写错了:你在第一个递归分支里扣的是
next_largest_coin(size)的面值,不是当前size本身。比如当前可用面值是1的时候,你直接把金额减了5,再带着最大面值1去递归,逻辑从根上就和找零问题的拆分方式错配了。 - 最大面值分支存在未捕获的类型错误:你调试时加的
if size ==25: print(25)其实已经能定位到问题点——代码打印出25之后就会直接触发错误。当递归走到size=25的分支时,代码会直接执行helper(n - next_largest_coin(size), size)的调用,此时next_largest_coin(25)返回None,相当于直接计算n - None,触发整数和None的减法错误——而你写的size == None判断根本覆盖不到这个场景,因为这个递归调用里传入的size参数还是25,不是None。 - 递归终止条件逻辑错误:你写的
if n <4: return 1把所有剩余金额小于4的场景都算成有效方案,完全违背找零问题的边界规则,正确的边界应该是金额刚好为0时(代表凑齐了)返回1,金额为负时(扣多了)返回0,不存在可用面值时返回0。
你前面三个小金额测试能通过,是因为15、10、20的金额都远小于25,根本触发不到size=25的崩溃分支,错配的扣减逻辑在小金额下刚好凑对了测试值,到100的金额时必然走到25面值的分支,直接计算失败拿不到正确结果。
Python中None的适用场景
None是Python内置的单例空值类型,适合的使用场景包括:
- 作为函数无显式返回值时的默认返回值
- 作为可选函数参数的占位默认值,用来区分用户传入的空参数和函数默认的空状态
- 用来标记某个变量没有绑定有效对象的状态
绝对不能把None直接用于数值计算、索引取值等需要具体类型值的场景,否则会触发类型错误
正确的修正思路
按照CS61A这道题的递归设计要求,调整方向如下:
- 把helper函数的递归逻辑理顺:定义
helper(n, max_coin)表示"凑金额n、允许使用的最大面值为max_coin的方案数",拆成两个独立子问题:- 子问题1:至少使用1枚max_coin面值的硬币,剩余金额为
n - max_coin,继续允许用最大面值max_coin凑剩余金额 - 子问题2:完全不使用max_coin面值的硬币,剩余金额n用比max_coin小一档的面值来凑
- 子问题1:至少使用1枚max_coin面值的硬币,剩余金额为
- 把
next_largest_coin的方向调整为返回比当前面值小的相邻面值:25对应10、10对应5、5对应1、1对应None,这样递归走到1面值的时候,就能正确触发"没有更小面值"的终止逻辑,不会出现None参与减法计算的问题 - 重写终止条件:
- n == 0时返回1(有效凑法)
- n < 0时返回0(超扣金额)
- max_coin为None时返回0(没有可用面值)
内容的提问来源于stack exchange,提问作者zengho
相关产品推荐
相关产品推荐

