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.
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.
A review. 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.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Aug 22, 2023 (edit).