coin change algorithm in scala using recursion

Question

I am trying to program the coin change problem in Scala using recursion. The code that i have written is as follows.

def countChange(money: Int, coins: List[Int]): Int = {
  def ways(change: List[Int], size: Int, capacity: Int): Int = {
    if(capacity == 0) 1
    if((capacity < 0) || (size <= 0)) 0

    //println and readLine to check and control each recursive call.

    println("calling ways(",change, change.length-1, capacity,") + ways(",change,   change.length, capacity - change(change.length - 1),")")
    readLine()
    //

    ways(change, change.length-1, capacity) + ways(change, change.length, capacity - change(change.length - 1))
  }
  ways(coins, coins.length, money)
}

On running the code, it does not terminate and keeps on calling the first recursive call. Where am I going wrong?

Answer 1

Nice and simple

def countChange(money: Int, coins: List[Int]): Int = {
  if(money == 0)
    1
  else if(money > 0 && !coins.isEmpty)
    countChange(money - coins.head, coins) + countChange(money, coins.tail)
  else
    0
}

Answer 2

Here is my implementation: I have tested it and it works fine

def countChange(money: Int, coins: List[Int]): Int = {

  def count(capacity: Int, changes: List[Int]): Int = {
    if (capacity == 0)
      1
    else if (capacity < 0)
      0
    else if (changes.isEmpty && capacity >= 1)
      0
    else
      count(capacity, changes.tail) 
        + count(capacity - changes.head, changes)
  }

  count(money, coins.sortWith(_.compareTo(_) < 0))
}