Skip to content

Instantly share code, notes, and snippets.

@zestime

zestime/countChange.scala

Created July 21, 2016 00:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save zestime/7cf0d554dc7f13baf0a911a183e2ff30 to your computer and use it in GitHub Desktop.
Save zestime/7cf0d554dc7f13baf0a911a183e2ff30 to your computer and use it in GitHub Desktop.
Download ZIP
Recursion problem from 'Functional Programming Principles in Scala'
Raw
countChange.scala
def countChange(money: Int, coins: List[Int]): Int =
money match {
case 0 => 1 // matched, add 1
case n => if (money < 0 || coins.isEmpty) 0 // not matched, ignored
else countChange(money - coins.head, coins) + countChange(money, coins.tail)
}
// test cases
assert(calculateCoins(4, List(1,2)) == 3)
assert(calculateCoins(300, List(5, 10, 20, 50, 100, 200, 500)) == 1022)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment