使用递归的scala中的硬币更改算法

Question

我试图使用递归编程Scala中的硬币更改问题.我写的代码如下.

def countChange(money: Int, coins: List[Int]): Int = {
  def ways(change: List[Int], size: Int, capacity: Int): Int = {
    if(capacity == 0) 1
    if((capacity < 0) || (size <= 0)) 0

    //println and readLine to check and control each recursive call.

    println("calling ways(",change, change.length-1, capacity,") + ways(",change,   change.length, capacity - change(change.length - 1),")")
    readLine()
    //

    ways(change, change.length-1, capacity) + ways(change, change.length, capacity - change(change.length - 1))
  }
  ways(coins, coins.length, money)
}

在运行代码时,它不会终止并继续调用第一个递归调用.我哪里错了？

Answer 1

很好,很简单

def countChange(money: Int, coins: List[Int]): Int = {
  if(money == 0)
    1
  else if(money > 0 && !coins.isEmpty)
    countChange(money - coins.head, coins) + countChange(money, coins.tail)
  else
    0
}

Answer 2

这是我的实现:我测试了它,它工作正常

def countChange(money: Int, coins: List[Int]): Int = {

    def count(capacity: Int, changes: List[Int]): Int = {
                if(capacity == 0) 
                  1
                else if(capacity < 0) 
                  0
                else if(changes.isEmpty && capacity>=1 )
                  0
                else
                        count(capacity, changes.tail) + count(capacity - changes.head, changes)
    }

    count(money, coins.sortWith(_.compareTo(_) < 0))
}

Answer 3

简单地说明一个值并不能使Scala返回它; 你需要一个明确的回报,或者它必须是最后一个项目.从而:

if (capacity == 0) return 1

要么

if (capacity == 0) 1
else if (...)
else { ... }

Answer 4

只是另一个解决方

def countChange(amount: Int, coins: List[Int]): Int = coins match {
  case _ if amount == 0 => 1
  case h :: t if amount > 0 => countChange(amount - h, h :: t) + countChange(amount, t)
  case _ => 0
}