Solve Coin Change Problems with both functional programming and tail recursion?

Question

I know how to solve Coin Change Problem with both imperative programming and DP.

I know how to solve Coin Change Problem with both FP and non-tail-recursion. But it will compute the same problem multiple times, which lead to inefficiency.

I know how to compute fibonacci number with both FP and DP/tail-recursion. Lots of articles use this example to explain "FP can be combined with DP" and "recursion can also be as efficient as loop".

But I don't know how to solve Coin Change Problem with both FP and DP/tail-recursion.

I think it's strange that articles on imperative programming will always mention the inefficiency of computing the same problem multiple times on Coin Change Problem, while those on FP just omit it.

In a more general sense, I wonder whether FP is powerful enough to solve such kind of "two dimensional" problem, while fibonacci is a "one dimensional" problem. Can anybody help me?

Coin Change Problem:

Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.

For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.

I meet this problem while I'm learning Scala, so use Scala to demonstrate the code if it's possible. Lisp will also be good. But I know little about Haskell.

http://stackoverflow.com/questions/15859432/stackoverflowerror-for-coin-change-in-scala — oluies, May 05 '15 at 06:13
@oluies But those answers in that link are not tail-recursion version. Not what I want. — Warbean, May 05 '15 at 06:43
OK, you usually can use an accumulator to convert it to tail recusive http://stackoverflow.com/questions/18945141/convert-normal-recursion-to-tail-recursion This one I dont know if you can do that with the generic case, if you make it more specific eg cents you should be able to use. Also memoization is used to limit memory needs and calculations — oluies, May 07 '15 at 21:29
There is a @tailrec way to solve the boolean variant of this problem (whether you can split the sum of money with available coins or not). In principle you can try to extend that to calculate all possible options as you need above... Requires trying out. — Alec, Apr 25 '21 at 06:18

score 0 · Answer 1 · edited Apr 26 '21 at 13:23

You may definitely find a big number of recursive implementations of coin-change problem over the internet, but hardly one solution that would be @tailrec.

If you look into the above-referenced discussions how to do @tailrec, e.g. Fibonacci sequence or Pascal Triangle problem, you may notice that they usually turn the approach ground-up —

instead of calling recursive function with smaller arguments, they start calculating with the smallest ones and recurse up through accumulating values until they hit required argument

How we can employ this approach to solve the coin change problem?

Let's try to imagine how we can accumulate possible sums of coins looping through all possible options... starting from initial set of coins. It pretty much resembles the solution tree. Assume available coin denominations are 1, 5 and 7.

         root      
         /|\       
        / | \      
       /  |  \     
      /   |   \    
     /    |    \   
    1     5     7  
   /|\   /|\   /|\ 
  1 5 7 1 5 7 1 5 7

Here comes the idea of the algorithm — for each node in the tree — spawn another subtree with all coin denominations as children, calculating sums as we go along the branches.

For simplicity — let's review a Boolean variant of coin-change problem, where you just need to answer (True/False) whether it's possible to split the sum with available set of coin denominations.

As long as we may hit the same sum via different branches, we'll be cutting-away repetitive sums with distinct.

  val coins = List(1, 5, 7)

  def canChange(sum: Int): Boolean = {

    @tailrec def canChangeInternal(possibleSums: List[Int]): Boolean = {
      val targetSums = possibleSums.distinct.filter(x => x <= sum)
      if (targetSums.isEmpty)
        false
      else if (targetSums.contains(sum))
        true
      else {
        val spawnedSums = targetSums.flatMap(x =>
          coins.map(coin => x + coin)
        )
        canChangeInternal(spawnedSums)
      }
    }

    canChangeInternal(coins)
  }

Actually in the above solution, one may use more effective collections for distinct values, such as HashSet if that might matter in practice.

In order to transition from the above Boolean-problem solution to the original problem — actually enlisting all possible split variants, you may need to do the following:

Maintain not just List of sums, but a List of tuples, where one of the tuple elements is a sum, and another one is the List consisting of coins how we reached to that sum.
We definitely wouldn't need to do distinct on sums, since one and the same sum might be accumulated via different options. We'd rather do a distinction on actual paths, since tree branches might just represent a re-ordering of the same elements. For the purpose of paths storage and comparison one may utilize a structure like SortedList or similar.
In order to enlist all possible options we are not POSITIVELY exiting the recursion with just contains, instead we would require all elements to satisfy == sum condition.
Last (but not least) — the return type of a @tailrec-function would be smth like List of Lists (or similar — depending on how you want to process it)

Solve Coin Change Problems with both functional programming and tail recursion?

1 Answers1