Scala中硬币变化的StackOverflowError? [英] StackOverflowError for coin change in Scala?
本文介绍了Scala中硬币变化的StackOverflowError?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在为 Scala 中的硬币(找零)问题编写递归函数.
I'm writing a recursive function for the Coin (change) problem in Scala.
我的实现因 StackOverflowError 而中断,我无法弄清楚为什么会发生这种情况.
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
这是我的电话:
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 语句:
I just added the else if statement in the mix:
else if(money<0)
combos
它摆脱了错误,但我的输出是 1500 东西 :( 我的逻辑有什么问题?
it got rid of the error but my output is 1500 something :( what is wrong with my logic?
推荐答案
以下是基于您的代码的正确解决方案:
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
}
这篇关于Scala中硬币变化的StackOverflowError?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文