StackOverflowError for coin change in Scala?

Question

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?

Answer 1

The first solution in the accepted answer has a redundant last parameter as noted by Paaro so I wanted to get rid of it. The second solution uses map which I wanted to avoid since it wasn't covered yet in the Week 1 or the Scala course I assume you're taking. Also, the second solution, as rightly noted by the author, would be way slower, unless it uses some memoization. Finally, Paaro's solution seems to have an unnecessary nested function.

So here's what I ended up with:

def countChange(money: Int, coins: List[Int]): Int =
  if (money < 0)
    0
  else if (coins.isEmpty)
    if (money == 0) 1 else 0
  else
    countChange(money, coins.tail) + countChange(money - coins.head, coins)

There is no need for braces here, as you can see.

I wonder if it could be further simplified.

Answer 2

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
}