Recursion

In recursion, we call a function inside another function's body. This is a powerful feature of Swift 5.8. In this way we have a powerful search capability.

With the func keyword, we specify a method. And when we invoke that same func in the method body, we have recursion. We compute all possible ways of counting 51 cents of change.

Our solution

Here we introduce two funcs: change and display. Let us start with change(). This function first tests to see if we have reached our goal amount (specified as 51 cents).

And If we have reached 51 cents exactly, we call display(), which loops through and displays the counts of all coin denominations.

Info We use a for-in loop on the amounts of coins and add only larger or equal-sized coins.

Next We copy our array of coins with an Array init. It is important to copy our array, as many code paths may act on the array argument.

Finally We use recursion to call the change() func from within change. No special keywords are needed.

func change(coins: [Int],
    amounts: [Int],
    highest: Int,
    sum: Int,
    goal: Int) {

    // See if our goal has been reached.
    if sum == goal {
        display(coins: coins, amounts: amounts)
        return
    }

    // Do not continue if we are past the goal.
    if sum > goal {
        return
    }

    // Try to add a coin in each possible size.
    for value in amounts {
        // Only add increasingly large coins.
        if value >= highest {
            // Copy the array and add this value to it.
            var copy = Array(coins)
            copy.append(value)
            // Try to add more coins.
            change(coins: copy,
                amounts: amounts,
                highest: value,
                sum: sum + value,
                goal: goal)
        }
    }
}

func display(coins: [Int], amounts: [Int]) {
    // Loop over amounts.
    for amount in amounts {
        // Count all coins with the current amount.
        var count = 0
        for coin in coins {
            if coin == amount {
                count += 1
            }
        }
        // Display the number of coins of this amount.
        print("\(amount): \(count)")
    }
    print("")
}

var coins: [Int] = []
var amounts: [Int] = [1, 5, 10, 25, 50]
// Start adding coins.
change(coins: coins,
    amounts: amounts,
    highest: 0,
    sum: 0,
    goal: 51)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

Initial call

We begin the program with an initial call to change(). We use an empty list of our current coins, and a table containing possible coin denominations (amounts).

SICP

The Structure and Interpretation of Computer programs is a fantastic book. This puzzle is adapted from it. The Swift language designers are almost certainly familiar with this book.

With loops (iteration) we can express recursion. But in programs, recursion has a sense of beauty that sometimes is lacking in loops. Swift supports recursive designs.