Python Recursion Example

Learn about recursion. Compute ways to count change using a recursive method.

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

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.

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

Python Recursion Example

Related Links:

.Net

Java

Related Links