Skip to content

Instantly share code, notes, and snippets.

@pdswan

pdswan/WaysToChange.hs

Last active August 29, 2015 14:05
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 pdswan/55786e9d8cec3366b5fe to your computer and use it in GitHub Desktop.
Save pdswan/55786e9d8cec3366b5fe to your computer and use it in GitHub Desktop.
Download ZIP
An illustration of the beauty of recursion and induction
Raw
WaysToChange.hs
waysToChange :: Int -> [Int] -> Int
waysToChange 0 _ = 1
waysToChange _ [] = 0
waysToChange amount denominations@(denomination:xs)
| amount < 0 = 0
| otherwise =
(waysToChange (amount - denomination) denominations) +
(waysToChange amount xs)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment