Recursion, rec. Suppose a pile of change is present: quarters, nickels, dimes. And 51 exact cents are needed. How many ways can we make 51 cents?
With recursion, we can compute all possibilities. We can exhaustively search. We generate all possible ways to make change with coins. We print all results.
Our solution. This may not be the most elegant solution possible. But it works. We introduce two functions: display (which displays coins) and change (which computes possibilities).
Info Display() loops over all amounts (denominations) and counts coins that were added of these sizes.
Next We use the Seq.where and Seq.length functions to improve counting of coins in the display function.
Detail Change() accepts 5 arguments. It sees if we have reached our goal amount (of 51 cents) and displays the result if we have.
And If we need more coins, we loop over amounts and only add larger or equal coins. We then add the new coin at the head of a list.
let display coins amounts =
// Loop over all coin sizes.// ... Count all coins for each size.// Print the results to the screen.
for amount in amounts do
// Use where to filter coins by amount.// ... Return the length of the matching sequence.
let count = Seq.where (fun x -> x = amount) coins
|> Seq.length
printfn "%d: %d" amount count
printfn ""
let rec change coins amounts highest sum goal =
// If correct sum of coins, display them.// ... If not enough coins, loop through and add new coins.
if sum = goal then display coins amounts
elif sum < goal then
// Loop over possible coin sizes.
for value in amounts do
// Only add larger coins.
if value >= highest then
// Place new coin at the start of the list (the head) and continue.
let copy = value :: coins
change copy amounts value (sum + value) goal
// Begin with these coins.
let coins = []
// Specify the amounts.
let amounts = [1; 5; 10; 25; 50]
// Call recursive function.
change coins amounts 0 0 511: 51
5: 0
10: 0
25: 0
50: 0
1: 46
5: 1
10: 0
25: 0
50: 0
1: 41
5: 2
10: 0
25: 0
50: 0
...
1: 1
5: 0
10: 0
25: 2
50: 0
1: 1
5: 0
10: 0
25: 0
50: 1
Recursive call. The change call in the body of the for-loop is a recursive call. We keep track of the sum of our change with an addition.
Info Let us consider the rec keyword—without rec we cannot use a recursive call. An error is reported.
error FS0039: The value or constructor 'change' is not defined
Smart compiler. If you are learning F# you are probably familiar with the Structure and Interpretation of Computer Programs. This example was based on a puzzle in SICP.
Further In SICP, the problem of efficiency for recursion is addressed. It is thought a "smart compiler" would make recursion fast.
And This is important to F# because recursion, and recursion-optimizing compilers, are essential to an effective F# environment.
A review. With recursion and appropriate logic we can solve many logic puzzles. Details are often a point of failure. And in puzzles like these there are many details.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Nov 19, 2023 (edit).