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.

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.

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.

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.