Scala中硬币更改的StackOverflowError？

Question

我正在为Scala中的Coin(更改)问题编写递归函数.

我的实现打破了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)
} 

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

else if(money<0)
    combos

它摆脱了错误,但我的输出是1500的东西:(我的逻辑有什么问题？

Answer 1

以下是基于您的代码的正确解决方案:

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

无论如何,有一个简短的解决方案(但效率不高,您可以缓存中间结果以使其高效.)

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
}

Answer 2

接受的答案中的第一个解决方案有一个冗余的最后一个参数,如Paaro所述,所以我想摆脱它.第二种解决方案使用map了我想要避免的,因为在第1周或Scala课程中我还没有涵盖,我认为你正在服用.此外,正如作者正确指出的那样,第二种解决方案会慢一些,除非它使用一些记忆.最后,Paaro的解决方案似乎有一个不必要的嵌套函数.

所以这就是我最终的结果:

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)

你可以看到,这里不需要括号.

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