Recursion. With recursion, we search for solutions, trying all possibilities. A recursive method should have a terminating condition (a goal).
Python notes. 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.
Info In the change call (near the bottom) we specify a target amount of 51 cents.
Important 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.
Next When we find a coin to add, in change, we copy our coins list with a slice. Then we append the new coin.
And It is important to copy, as each recursive call must have its own list. When we reach our goal amount, we display our coins.
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 notes. The 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.
Tip When using recursion, it is critical to add checks (such as if-statements) in the recursive method.
Info If-statements limit the depth of recursion. In our example, there is no point to continue past 51 cents (our goal).
And We only add coins of greater or equal value as we progress (in change). This makes the search much simpler as well.
SICP. 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.
Tip Solving game problems, like puzzles, with recursive methods like this one is an excellent learning exercise.
A recursive method can solve many problems simply by trying every possible option. The change puzzle here is solved in a brute-force way.
Dot Net Perls is a collection of pages with code examples, which are updated to stay current. Programming is an art, and it can be learned from examples.
Donate to this site to help offset the costs of running the server. Sites like this will cease to exist if there is no financial support for them.
Sam Allen is passionate about computer languages, and he maintains 100% of the material available on this website. He hopes it makes the world a nicer place.
This page was last updated on Jun 26, 2023 (edit).