Scala - Recursion Example (Tail Recursion)

Recursion. 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.

A solution. 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.

Info In the 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.

Tip Lists are immutable, so the "copy" list is separate in memory from all other lists.

List

Finally When we find the goal amount of coins (51 cents) we loop over all denominations and count coins added.

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

Lambda. 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.

def

Info At the bottom of the example we create a List of amounts (pennies, nickels, dimes, quarters). Our starting List of coins is empty.

SICP. 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.

Detail In the book, we want to count all possible ways of making change. This program just lists them—it does not count them.

Summary. Recursion allows us to brute-force solve a puzzle. Adding appropriate constraints (like if-statements) is key. Exact coding and careful testing is needed.