MakeChange

gistfile1.fs

let makeChange amount =
    let rec doChange amount soFar coins =
        match coins with
        |coin :: _ when amount >= coin ->
            doChange (amount - coin) (coin :: soFar) coins
        |_ :: rest -> 
            doChange amount soFar rest
        |[] -> soFar
    doChange amount [] [25; 10; 5; 1]

// test

for x in 0..10 do (x, makeChange x) ||> printfn "%d -> %A"

// output

0 -> []
1 -> [1]
2 -> [1; 1]
3 -> [1; 1; 1]
4 -> [1; 1; 1; 1]
5 -> [5]
6 -> [1; 5]
7 -> [1; 1; 5]
8 -> [1; 1; 1; 5]
9 -> [1; 1; 1; 1; 5]
10 -> [10]