**Python Recursion Example**Learn about recursion. Compute ways to count change using a recursive method.

dot net perls

**Recursion.** With recursion, we search for solutions, trying all possibilities. A recursive method should have a terminating condition (a goal). And in a loop, it 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. In the change call (near the bottom) we specify a target amount of 51 cents.

**Change** This 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.

for

**Info** 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.

Copy List

**Display** This def-method loops over all possible amounts, and displays the number of coins collected by amount.

Python program that uses recursion

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

**The output** contains many possible coin assortments to make 51 total cents. We first learn we can use 51 one-cent pieces. Next we can use 46 one-cent pieces and 1 five-cent piece. These both total to 51 cents each.

**Finally** In the last result, shown after many skipped results, we use 1 one-cent coin and a 50-cent coin.

**When using recursion,** it is critical to add checks (such as if-statements) in the recursive method. These 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. Many problems can be solved this way.

**Tip** Solving game problems, like puzzles, with recursive methods like this one is an excellent learning exercise.

**Summary.** A recursive method can solve many problems simply by trying every possible option. The change puzzle here is solved in a brute-force way. We try every possible coin at every level of recursion.

© 2007-2021 sam allen. send bug reports to info@dotnetperls.com.