将一个递归函数重构为迭代函数，解决硬币找零类型的问题。

Question

在一个“零钱找零”类型的问题中，我试图将递归函数重构为迭代函数。给定一组硬币类型 coin_types，函数 coinr 通过递归查找支付给定金额 sum 的最少硬币数量。

# Any coin_type could be used more than once or it may not be used at all

sub coinr ($sum, @coin_types) { # As this is for learning basic programming 
    my $result = $sum;          # No memoization (dynamic programming) is used
    if $sum == @coin_types.any { return 1 }
    else { for @coin_types.grep(* <= $sum) -> $coin_type {
        my $current = 1 + coinr($sum - $coin_type, @coin_types);
        $result = $current if $current < $result; } }
    $result;
}

say &coinr(@*ARGS[0], split(' ', @*ARGS[1])); 

# calling with
# 8 "1 4 5" gives 2 (4+4)
# 14 "1 3 5" gives 4 (1+3+5+5), etc.

这个函数最初是用Python编写的，我将其转换为了Raku。这是我的迭代版本，但它非常不完整：

# Iterative

sub coini ($sum, @coin_types) {
    my $result = 1;
    for @coin_types -> $coin_type {
    for 1 ... $sum -> $i {
        if $sum-$coin_type == @coin_types.any { $result += 1 } #?
        else { # ???
        }
     }
   }
}

有人可以帮我解决这个问题吗？

- Lars Malmsteen

Answer 1

有许多不同的迭代实现方式（正如我们所说的：“做事情的方法不止一种！”）。 下面是一种方法：

sub coini($sum is copy, @coin-types) {
    gather while $sum > 0 { take $sum -= @coin-types.grep(* ≤ $sum).max } .elems
}

这会将 (现在是可变的) $sum 减去最大可能的硬币，并将当前 $sum 记录在列表中。然后，由于我们只想知道硬币数量，它返回该列表的长度。

- codesections

---

这是gather/take结构的一个很好的例子，展示了如何通过is copy特性在函数内部使用参数。 - Lars Malmsteen