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))
}

Answer 3

Just another solution

def countChange(amount: Int, coins: List[Int]): Int = coins match {
  case _ if amount == 0 => 1
  case h :: t if amount > 0 => countChange(amount - h, h :: t) + countChange(amount, t)
  case _ => 0
}

Answer 4

Simply stating a value does not make Scala return it; you either need an explicit return, or it has to be the last item stated. Thus:

if (capacity == 0) return 1

or

if (capacity == 0) 1
else if (...)
else { ... }

Answer 5

Hey I just thought it would be better to see not only the amount but also the list of them, so put on top of the above example like :

def moneyChanges(money: Int, coins: List[Int]) : Option[List[Seq[Int]]]= {
  var listOfChange=List[Seq[Int]]()
  def changeMoney(capacity: Int, changes: List[Int], listOfCoins: Option[Seq[Int]]): Int = {
    if (capacity == 0) {
      listOfChange = listOfCoins.get :: listOfChange
      1
    } else if (capacity < 0)
      0
    else if (changes.isEmpty && capacity >= 1)
      0
    else {
      changeMoney(capacity, changes.tail, listOfCoins) +
      changeMoney(capacity - changes.head, changes, 
      Some(changes.head +: listOfCoins.getOrElse(Seq())))
    }
  }

  changeMoney(money, coins.sortWith(_.compareTo(_) < 0), None)
  Some(listOfChange)
}

Answer 6

Here is my code: It's not optimized but works on all test cases.

The idea is to subtract first coin of list from from money until it becomes 0. Once it becomes 0, it will return 1 which means one solution is possible. To add all solutions coming from different recursion I used foldLeft.

(iterating list using foldLeft, so first goes in 1, then again goes in recursion and iterate for (1, 2) list)

                    [4, (1, 2)].  
             /(1 as cn)       \ (2 as cn)
            [3, (1, 2)].                 [2, (2)]
         /(-1)       \(-2)                \
      [2, (1, 2)].     [1, (2)].          [0, (2)]   
       /.(-1)    \(-2) 
     [1, (1, 2)].   [0, (2)]
      /. (-1)  \(-2)
    [0, (1, 2)].  [-1, (2)]

def countChange(money: Int, coins: List[Int]): Int = coins.foldLeft(0)((accum, cn) =>
  (money, cn) match {
    case (money, _) if money < 0 => 0
    case (0, _) => 1
    case (curr_money, curr_coin) =>
      val (before_curr_coin, after_curr_coin) = coins.span(_ != curr_coin)
      accum + countChange(curr_money - curr_coin, after_curr_coin)
  })

Answer 7

here is a DP approach to reduce a lot of re-calculation in recursive approach

object DP {
  implicit val possibleCoins = List(1, 5, 10, 25, 100)
  import collection.mutable.Map

  def countChange(amount: Int)(implicit possibleCoins: List[Int]) = {
    val min = Map((1 to amount).map (_->Int.MaxValue): _*)
    min(0) = 0
    for {
      i <- 1 to amount
      coin <- possibleCoins
      if coin <= i && min(i - coin) + 1 < min(i)
    } min(i) = min(i-coin) + 1
    min(amount)
  }

  def main(args: Array[String]) = println(countChange(97))
}

see DP from novice to advanced for algorithm

Answer 8

Below code is similar to one of the above example except I am using match case instead of if else

def countChange(money: Int, coins: List[Int]): Int = {
    def change(m: Int, coinList: List[Int], count: Int): Int =
      m match {
        case _ if m < 0 => count
        case _ if coinList.isEmpty => {
          m match {
            case 0 => count + 1
            case _ => count
          }
        }
        case _ => change(m, coinList.tail, count) + change(m - coinList.head, coinList, count)
      }
    change(money, coins, 0)
  }

Answer 9

This will handle the case where money is zero but not negative coins...

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

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

    if(money == 0) {
      0
    } else {
      loop(money: Int, coins: List[Int])
    }

}