F# Recursion Example: rec Keyword

Use the rec keyword to compute change in a recursive function. Compute all possibilities for an amount of coins.

Recursion, rec. 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).

Display: This loops over all amounts (denominations) and counts coins that were added of these sizes.

Seq: We use the Seq.where and Seq.length functions to improve counting of coins in the display function.

Seq

Change: This function accepts 5 arguments. It sees if we have reached our goal amount (of 51 cents) and displays the result if we have.

For: 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.

F# program that computes coins with rec function 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 51 Output 1: 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.

Rec keyword. Let us consider the rec keyword at the start of our recursive function. Without rec we cannot use a recursive call. An error is reported.

Rec keyword error: 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 (and some luck) we can solve many logic puzzles. Details are often a point of failure. And in puzzles like these there are many details.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

F# Recursion Example: rec Keyword

Related Links:

.Net

Java

Related Links