Swift Recursion

Use recursion to compute all possibilities for a puzzle. Use an array to keep track of coins.

Recursion. We call a func in a loop. And sometimes we call a func in another func. This is recursion. We create 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.

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

For

Array: 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.

Array

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

Swift program that uses recursion func change(coins: [Int], amounts: [Int], highest: Int, sum: Int, goal: Int) { // See if our goal has been reached. if sum == goal { display(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(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++ } } // 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, amounts: amounts, highest: 0, sum: 0, goal: 51) Output 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.

Quote: We can easily translate this description into a recursive procedure (Structure and Interpretation of Computer Programs).

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

Swift Recursion

Related Links:

.Net

Java

Related Links