In recursion a method calls itself. This enables a powerful, exhaustive search. We can compute all possibilities. We can compute everything.
In the Wizard Book, a puzzle is provided. How many ways can we make change with a pile of coins? We can use 1, 5, 10, 25, 50 cent pieces. We use recursion to search for all answers.
We introduce the change()
and display()
functions. With change()
we compute possible arrangements of coins until we meet our goal amount. We only add equal or larger coins.
for
-loop we try to add coins. When we find a coin of equal or larger denomination we add it to the head of a list.def change(coins: List[Int], amounts: List[Int], highest: Int, sum: Int, goal: Int): Unit = { // See if we have reached the total sum of coins. // ... Display our results if we have. if (sum == goal) { display(coins, amounts) } else if (sum < goal) { // We still need to add coins. for (value <- amounts) { // Only add higher or equal coins than before. if (value >= highest) { // Add the new value to the start of a list. val copy = value :: coins // Continue adding new coins. change(copy, amounts, value, sum + value, goal) } } } } def display(coins: List[Int], amounts: List[Int]): Unit = { // Loop over all coin sizes. for (amount <- amounts) { // Count total number of coins of that type. val count = coins.count(_ == amount) // Display our coins. println(s"$amount: $count") } println() } object Program { def main(args: Array[String]): Unit = { // We start with no coins. val coins = List() // Coin sizes. val amounts = List(1, 5, 10, 25, 50) // Begin counting change. change(coins, amounts, 0, 0, 51) } }1: 51 5: 0 10: 0 25: 0 50: 0 1: 46 5: 1 10: 0 25: 0 50: 0 ... 1: 1 5: 0 10: 5 25: 0 50: 0 1: 1 5: 0 10: 0 25: 2 50: 0 1: 1 5: 0 10: 0 25: 0 50: 1
To display coins, we use a lambda expression with the count()
function. The underscore is "each value" in the List
. We count each coin with a matching value.
List
of amounts (pennies, nickels, dimes, quarters). Our starting List
of coins is empty.This puzzle was adapted from an example is The Structure
and Interpretation of Computer Programs (the wizard book). Scala is not Scheme, but it can compute things well.
Recursion allows us to brute-force solve a puzzle. Adding appropriate constraints (like if
-statements) is key. Exact coding and careful testing is needed.