Scalaのコイン変更のStackOverflowError？

Question

私はScalaのCoin (change) problemの再帰関数を書いています。

私の実装はStackOverflowErrorで壊れてしまい、なぜそれが起こるのか理解できません。これは私の定義である

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

：

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 

この

は私の呼び出しです

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(money<0) 
    combos 

：私はちょうどミックス内の他のif文を追加しました

それはエラーを取り除いたが、私の出力は1500何か:(w帽子は私の論理に間違っていますか？ここで

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

@Eastsunソリューションは良いのですが、原因、それにお金= 0が1ではなく0を返しますが、あなたは簡単にそれを修正することができたときに、それは失敗します。

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) 
    if(money>0) recurs(money, coins, 0) else 0 
} 

Answer 3

実際には蓄積されないcntパラメータを省略することができます。

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 
} 

Answer 4

the accepted answerの最初のソリューションは、私はそれを取り除くために望んでいた最後のパラメータas noted by Paaro冗長を持っています。再発する機能は、常に最適化されたアルゴリズムは次のようになりますので、0または1のいずれかを返します。 2番目の解決方法は、を使用しました。私が避けたかったのは、1週間目またはScalaコースではまだカバーされていなかったからです。また、著者が正しく述べたように、2番目の解決方法は、メモを使用しない限り、遅くなります。最後に、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) 

：

は、だからここに私がしてしまったものです。

さらに簡素化できるのだろうかと思います。ここ

Answer 5

は

object DP { 
    implicit val possibleCoins = List(1, 5, 10, 25, 100) 
    import collection.mutable.Map 

    def countChange(amount: Int)(implicit possibleCoins: List[Int]) = { 
    val min = Map((1 to amount).map (_->Int.MaxValue): _*) 
    min(0) = 0 
    for { 
     i <- 1 to amount 
     coin <- possibleCoins 
     if coin <= i && min(i - coin) + 1 < min(i) 
    } min(i) = min(i-coin) + 1 
    min(amount) 
    } 

    def main(args: Array[String]) = println(countChange(97)) 
} 

あなたは `recurs`（`再発する（お金、コインの2回目の呼び出しだアルゴリズム