递归调用中如何追踪最小值？无全局变量实现最小硬币找零

你当前用全局变量实现了递归找最小硬币数的功能，确实全局变量会带来副作用（比如多次调用函数时需要重置全局变量），可以通过让递归函数直接返回当前状态的最小硬币数来避免全局变量，以下是具体实现方案：

原代码回顾 #

minres = 10000
def count(sum, i, coins, temp, res):
    global minres
    if sum == 0:
        minres = min(minres, res)
        return

    if sum < 0:
        return

    if i == len(coins):
        return

    temp.append(coins[i])
    count(sum-coins[i], i, coins, temp, res+1)
    temp.pop()
    count(sum, i+1, coins, temp, res)

    return minres


coins = [9, 6, 5, 1]
print(count(11, 0, coins, [], 0))

改进后的无全局变量实现 #

核心思路是让递归函数返回当前剩余金额、当前硬币索引下的最小硬币数，通过递归调用的返回值比较选择最优解，同时去掉不需要的temp参数（仅需数量时无需跟踪具体硬币）：

def count(remaining_sum, coin_idx, coins):
    # 边界条件：剩余金额为0，说明凑成了，需要0个额外硬币
    if remaining_sum == 0:
        return 0
    # 剩余金额不足或无硬币可选，返回极大值表示该路径不可行
    if remaining_sum < 0 or coin_idx == len(coins):
        return float('inf')
    
    # 选择当前硬币：递归计算剩余金额的最小硬币数 + 1（当前用了一个硬币）
    choose = count(remaining_sum - coins[coin_idx], coin_idx, coins) + 1
    # 不选择当前硬币：递归处理下一个硬币
    not_choose = count(remaining_sum, coin_idx + 1, coins)
    
    # 返回两种选择中的最小值
    return min(choose, not_choose)


coins = [9, 6, 5, 1]
result = count(11, 0, coins)
# 若结果为极大值则表示无法凑出目标金额，这里题目场景可凑出
print(result if result != float('inf') else -1)  # 输出2

方案说明 #

• 纯函数设计：函数仅依赖输入参数，无外部状态依赖，多次调用不会出现全局变量污染问题
• 逻辑清晰：每个递归分支明确返回当前状态的最优解，通过min函数直接比较两种选择的结果
• 冗余参数移除：去掉了原代码中用于跟踪硬币的temp参数，仅保留核心的剩余金额和硬币索引参数

内容的提问来源于stack exchange，提问作者Pranav Narayan