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.

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.