硬币找零类问题中将递归函数重构为迭代形式的实现咨询

你提供的递归版本通过深度优先搜索枚举所有合法硬币组合，未使用记忆化/动态规划优化，以下是完全对齐该逻辑的迭代实现，使用显式栈模拟递归的调用过程：

# 迭代版：完全对齐原递归逻辑，无额外优化，仅用栈模拟递归调用
sub coini ($sum, @coin_types) {
    # 初始化最坏结果：全用面额为1的硬币，总数等于目标金额
    my $result = $sum;
    # 栈存储每个分支的状态：(剩余待凑金额, 已使用硬币数量)
    my @call_stack = [ $sum, 0 ];

    while @call_stack {
        my ($current_sum, $used_count) = @call_stack.pop;
        # 对齐原递归终止条件：剩余金额刚好是某一枚硬币的面额
        if $current_sum == @coin_types.any {
            my $total = $used_count + 1;
            $result = $total if $total < $result;
            next;
        }
        # 遍历所有可用硬币，压入新的分支状态，对应原递归的函数调用
        for @coin_types.grep(* <= $current_sum) -> $coin {
            @call_stack.push: [ $current_sum - $coin, $used_count + 1 ];
        }
    }
    return $result;
}

# 测试用例和原递归完全一致
say coini(8, <1 4 5>); # 输出 2
say coini(14, <1 3 5>); # 输出 4
say &coini(@*ARGS[0], split(' ', @*ARGS[1])); 

原尝试代码的问题说明 #

你之前写的双重循环没有维护每个枚举分支的状态，无法覆盖所有可能的硬币组合，因此无法得到正确结果。本次实现的迭代版和原递归逻辑1:1对齐，适合用于学习递归转迭代的基础原理。

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