StackOverflowError for coin change in Scala?

scala

Solution

Here is the correct solution based on your codes:

def countChange(money: Int, coins: List[Int]): Int = {
  def recurs(m: Int, cs: List[Int], cnt: Int): Int =
      if(m < 0) cnt  //Not a change, keep cnt
      else if(cs.isEmpty) {
        if(m == 0) cnt + 1 else cnt // plus cnt if find a change
      }
      else recurs(m, cs.tail, cnt) + recurs(m-cs.head, cs, cnt)
  recurs(money, coins, 0)
}

Anyway, there is a short solution(But not efficient, you can cache the middle result to make it efficient.)

def countChange(m: Int, cs: List[Int]): Int = cs match {
  case Nil => if(m == 0) 1 else 0
  case c::rs => (0 to m/c) map (k => countChange(m-k*c,rs)) sum
}

Problem

I'm writing a recursive function for the Coin (change) problem in Scala. My implementation breaks with StackOverflowError and I can't figure out why it happens. ``` Exception in thread "main" java.lang.StackOverflowError at scala.collection.immutable.$colon$colon.tail(List.scala:358) at scala.collection.immutable.$colon$colon.tail(List.scala:356) at recfun.Main$.recurs$1(Main.scala:58) // repeat this line over and over ``` this is my call: ``` println(countChange(20, List(1,5,10))) ``` this is my definition: ``` def countChange(money: Int, coins: List[Int]): Int = { def recurs(money: Int, coins: List[Int], combos: Int): Int = { if (coins.isEmpty) combos else if (money==0) combos + 1 else recurs(money,coins.tail,combos+1) + recurs(money-coins.head,coins,combos+1) } recurs(money, coins, 0) } ``` Edit: I just added the else if statement in the mix: ``` else if(money<0) combos ``` it got rid of the error but my output is 1500 something :( what is wrong with my logic?

Original source