With recursion, we search for solutions, trying all possibilities. A recursive method should have a terminating condition (a goal).
We can use Python to develop recursive algorithms. In a loop, a recursive method can call itself with varying arguments. In this way the search branches out.
This program begins with an empty coins list, where the final coins are stored. It also specifies the possible amounts of coins, such as 1 or 5 cents each.
Change()
is a recursive method—it first checks to see if we have collected our goal amount. Then it tries to add new coins in a loop.Display()
loops over all possible amounts, and displays the number of coins collected by amount.def change(coins, amounts, highest, sum, goal): # See if we are done. if sum == goal: display(coins, amounts) return if sum > goal: return for value in amounts: if value >= highest: # Copy the coins list, then add the current value. copy = coins[:] copy.append(value) # Recursively add more coins. change(copy, amounts, value, sum + value, goal) def display(coins, amounts): # Display our coins sorted by amount. for amount in amounts: count = coins.count(amount) print(amount, ":", count) print("") coins = [] amounts = [1, 5, 10, 25, 50] # Begin. 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 : 0 25 : 0 50 : 1
Program
notesThe output has possible coin assortments to make 51 total cents. We first learn we can use 51 one-cent pieces. In the last result we use 1 one-cent coin and a 50-cent coin.
if
-statements) in the recursive method.If
-statements limit the depth of recursion. In our example, there is no point to continue past 51 cents (our goal).This example is taken from the Structure
and Interpretation of Computer Programs, a classic programming text. Recursion is a way to apply a brute-search to a problem.
A recursive method can solve many problems simply by trying every possible option. The change puzzle here is solved in a brute-force way.