如何用递归SQL解决优先使用大面额的硬币找零问题

需求说明 #

实现硬币找零的贪心算法：优先使用大面额硬币（面额顺序为10→5→2→1），通过递归SQL完成计算，最终输出各面额硬币的使用次数。

现有表结构 #

coin表存储可用硬币面额：

找零过程示例（以43元为例） #

43 - 10 = 33 → 33 - 10 = 23 → 23 - 10 = 13 → 13 - 10 = 3（无法再减10）
3 无法减5
3 - 2 = 1（无法再减2）
1 - 1 = 0（结束）

期望输出 #

最终需要统计各面额的使用次数：

递归SQL实现方案 #

以下是基于标准SQL的递归CTE实现，适用于支持递归CTE的数据库（如PostgreSQL、MySQL 8.0+、SQL Server等）：

WITH RECURSIVE change_process AS (
    -- 初始步骤：设定找零目标金额，从最大面额开始
    SELECT 
        c.id,
        c.coin,
        43 AS remaining, -- 目标找零金额，可替换为变量
        CASE WHEN c.coin <= 43 THEN 1 ELSE 0 END AS cnt
    FROM coin c
    ORDER BY c.coin DESC
    LIMIT 1
    UNION ALL
    -- 递归步骤：迭代处理剩余金额，切换面额或累计计数
    SELECT
        CASE 
            WHEN cp.coin <= (cp.remaining - cp.cnt * cp.coin) THEN cp.id
            ELSE (SELECT id FROM coin WHERE coin < cp.coin ORDER BY coin DESC LIMIT 1)
        END AS id,
        CASE 
            WHEN cp.coin <= (cp.remaining - cp.cnt * cp.coin) THEN cp.coin
            ELSE (SELECT coin FROM coin WHERE coin < cp.coin ORDER BY coin DESC LIMIT 1)
        END AS coin,
        CASE 
            WHEN cp.coin <= (cp.remaining - cp.cnt * cp.coin) THEN cp.remaining - cp.cnt * cp.coin - cp.coin
            ELSE cp.remaining - cp.cnt * cp.coin
        END AS remaining,
        CASE 
            WHEN cp.coin <= (cp.remaining - cp.cnt * cp.coin) THEN cp.cnt + 1
            ELSE CASE WHEN (SELECT coin FROM coin WHERE coin < cp.coin ORDER BY coin DESC LIMIT 1) <= (cp.remaining - cp.cnt * cp.coin) THEN 1 ELSE 0 END
        END AS cnt
    FROM change_process cp
    WHERE (cp.remaining - cp.cnt * cp.coin) > 0 -- 剩余金额不为0则继续递归
),
-- 汇总各面额使用次数，补充未使用的硬币
final_counts AS (
    SELECT 
        id,
        MAX(cnt) AS count
    FROM change_process
    GROUP BY id
    UNION ALL
    SELECT 
        id,
        0 AS count
    FROM coin
    WHERE id NOT IN (SELECT id FROM change_process)
)
-- 按id降序输出结果
SELECT id, count
FROM final_counts
ORDER BY id DESC;

逻辑说明 #

1. 递归初始层：从最大面额硬币切入，初始化剩余金额为目标值，判断当前面额是否可用，计数初始化为1或0。
2. 递归迭代层：
   • 若当前面额仍能覆盖剩余金额，继续使用该面额，计数+1，剩余金额减去对应面额。
   • 若当前面额无法使用，切换到下一个更小面额，重置计数为1（新面额可用时）或0，剩余金额保持不变。
3. 终止条件：剩余金额减至0时停止递归。
4. 结果汇总：提取各面额的最大计数作为总使用次数，补充未被使用的硬币（计数为0），最后按id降序输出。

注意事项 #

• 目标金额（示例中的43）可替换为变量或参数，适配不同找零需求。
• 依赖coin表中硬币面额的存储逻辑，通过ORDER BY coin DESC保证贪心顺序。
• 不同数据库的递归CTE语法细节可能有差异，需根据实际环境调整。

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