scala - Scala 中硬币找零的 StackOverflowError？

Question

我正在为 Coin (change) problem 编写一个递归函数在 Scala 中。

我的实现因 StackOverflowError 而中断，我无法弄清楚为什么会发生这种情况。

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

这是我的电话:

  println(countChange(20, List(1,5,10)))

这是我的定义:

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

编辑:我刚刚在组合中添加了 else if 语句:

else if(money<0)
    combos

它消除了错误，但我的输出是 1500 左右:(我的逻辑出了什么问题？

Answer 1

the accepted answer中的第一个解决方案有一个多余的最后一个参数 as noted by Paaro所以我想摆脱它。第二个解决方案使用 map ，我想避免使用它，因为我假设您正在学习的第一周或 Scala 类(class)中尚未涵盖它。此外，正如作者正确指出的那样，第二种解决方案会慢得多，除非它使用一些内存。最后，Paaro's solution似乎有一个不必要的嵌套函数。

这就是我最终得到的结果:

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)

如您所见，这里不需要大括号。

我想知道是否可以进一步简化。