**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*)
**Output**
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

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