StackOverflowError for coin change in Scala?

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.

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
}

One can omit the cnt parameter, which is, in fact, never accumulated. The recurs function always returns either 0 or 1, so the optimized algorithm would be:

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