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

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?

Solution

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.

- How to loop over a multidimensional objectArray with Smarty?
- TypeScript recursive union function type
- Time complexity for recursive binary search that also prints current subarray
- How can I fix an error the error `Cannot build rewrite system for generic signature; rule length limit exceeded` in swift?
- Find the parent element of an array by the id of its child
- recursion on nested list need some support
- How do you prove termination of a recursive list length?
- python recursion i dont understand this output pls help me
- Why does recursively running `joblib.Parallel` increases the computation time?
- I'm trying to understand recursion in Tcl, but every time the recursion finishes it throws errors
- How to remove all numbers from a list in Lisp
- Calculate the total weight of segments
- Why does the expression !(cin>>word) cause infinite recursion?
- What's the best way to recursively traverse a BinaryTree in Java without void methods?
- can anybody explains the code and also recursion tree
- Is it possible to limit the depth of a recursive directory listing in S3 bucket?
- takeWhile implementation in JavaScript - Looking for better ideas
- I used a recursive function to modify a string, but if the string is too large the function returns nothing
- How to Compress Paths in SQL Server Using Recursive CTE with Node Visibility Conditions?
- Why this recursion example in ocaml doesn't work for negative number?
- Recursive loop on a list to print xml with indent
- Big O of algorithm that steps over array recursively
- Powerset of a list with equal elements in Java
- Recursion in FP-Growth Algorithm
- Passing list to function results in no case clause matching
- Convert tree-like structure formatted as a string using indentations to a list of paths
- Recursive function fails depending on lexical scoping
- Creating a list of interleaved elements: Prolog
- How to get the recursive difference formula between two columns in excel
- Get all values and associative keys as a flat array from a multidimensional array of variable depth/structure