алгоритм обмена монет в scala с использованием рекурсии

Простое указание значения не означает, что Scala возвращает его; вам либо нужен явный возврат, либо это должен быть последний указанный элемент. Таким образом:

if (capacity == 0) return 1

or

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

Красиво и просто

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
}

Вот моя реализация: я протестировал ее, и она отлично работает

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

Просто другое решение

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
}

Эй, я просто подумал, что было бы лучше видеть не только количество, но и их список, поэтому поместите поверх приведенного выше примера, например:

def moneyChanges(money: Int, coins: List[Int]) : Option[List[Seq[Int]]]= {
  var listOfChange=List[Seq[Int]]()
  def changeMoney(capacity: Int, changes: List[Int], listOfCoins: Option[Seq[Int]]): Int = {
    if (capacity == 0) {
      listOfChange = listOfCoins.get :: listOfChange
      1
    } else if (capacity < 0)
      0
    else if (changes.isEmpty && capacity >= 1)
      0
    else {
      changeMoney(capacity, changes.tail, listOfCoins) +
      changeMoney(capacity - changes.head, changes, 
      Some(changes.head +: listOfCoins.getOrElse(Seq())))
    }
  }

  changeMoney(money, coins.sortWith(_.compareTo(_) < 0), None)
  Some(listOfChange)
}

вот подход DP, чтобы уменьшить количество пересчетов в рекурсивном подходе

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

см. DP от новичка к продвинутому для алгоритма

Код ниже аналогичен одному из приведенных выше примеров, за исключением того, что я использую регистр соответствия вместо if else

def countChange(money: Int, coins: List[Int]): Int = {
    def change(m: Int, coinList: List[Int], count: Int): Int =
      m match {
        case _ if m < 0 => count
        case _ if coinList.isEmpty => {
          m match {
            case 0 => count + 1
            case _ => count
          }
        }
        case _ => change(m, coinList.tail, count) + change(m - coinList.head, coinList, count)
      }
    change(money, coins, 0)
  }

Вот мой код: он не оптимизирован, но работает во всех тестовых случаях.

Идея состоит в том, чтобы вычесть первую монету из списка из денег, пока она не станет 0. Как только она станет 0, она вернет 1, что означает, что возможно одно решение. Чтобы добавить все решения, полученные из разных рекурсий, я использовал foldLeft.

(итерация списка с использованием foldLeft, поэтому сначала идет 1, затем снова идет рекурсия и итерация для (1, 2) списка)

                [4, (1, 2)].  
         /(1 as cn)       \ (2 as cn)
        [3, (1, 2)].                 [2, (2)]
     /(-1)       \(-2)                \
  [2, (1, 2)].     [1, (2)].          [0, (2)]   
   /.(-1)    \(-2) 
 [1, (1, 2)].   [0, (2)]
  /. (-1)  \(-2)
[0, (1, 2)].  [-1, (2)]


def countChange(money: Int, coins: List[Int]): Int = coins.foldLeft(0)((accum, cn) =>
  (money, cn) match  {
    case (money, _) if money < 0 => 0
    case (0, _) => 1
    case (curr_money, curr_coin) => {
      val (before_curr_coin, after_curr_coin) = coins.span(_ != curr_coin)
      accum + countChange(curr_money - curr_coin, after_curr_coin)
    }
})