TheDeveloperBlog.com

Home | Contact Us

C-Sharp | Java | Python | Swift | GO | WPF | Ruby | Scala | F# | JavaScript | SQL | PHP | Angular | HTML

<< Back to F#

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.
© TheDeveloperBlog.com
The Dev Codes

Related Links:


Related Links

Adjectives Ado Ai Android Angular Antonyms Apache Articles Asp Autocad Automata Aws Azure Basic Binary Bitcoin Blockchain C Cassandra Change Coa Computer Control Cpp Create Creating C-Sharp Cyber Daa Data Dbms Deletion Devops Difference Discrete Es6 Ethical Examples Features Firebase Flutter Fs Git Go Hbase History Hive Hiveql How Html Idioms Insertion Installing Ios Java Joomla Js Kafka Kali Laravel Logical Machine Matlab Matrix Mongodb Mysql One Opencv Oracle Ordering Os Pandas Php Pig Pl Postgresql Powershell Prepositions Program Python React Ruby Scala Selecting Selenium Sentence Seo Sharepoint Software Spellings Spotting Spring Sql Sqlite Sqoop Svn Swift Synonyms Talend Testng Types Uml Unity Vbnet Verbal Webdriver What Wpf