Refactoring a recursive function into iterative in a coin-change type of problem

Question

In a coin-change type of problem, I'm trying to refactor the recursive function into iterative. Given a set of coin_types, the function coinr finds the minimum number of coins to pay a given amount, sum, recursively.

# 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.

This function was originally written in Python and I converted it to Raku. Here is my take on the iterative version, which is very incomplete:

# 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 { # ???
        }
     }
   }
}

Can somebody help me on this?

Nafis

Answer 1

There are a number of different ways to implement this iteratively (There's More Than One Way To Do It, as we like to say!) Here's one approach:

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

This decreases the (now mutable) $sum by the largest coin possible, and keeps track of the current $sum in a list. Then, since we only want the number of coins, it returns the length of that list.

Iminourea

This is a good example of the gather/take construct and shows how to use an argument inside the function by the is copy trait. – Nafis