Introduction to Python Programming

# 12.5Using recursion to solve problems

Introduction to Python Programming12.5 Using recursion to solve problems

## Learning objectives

By the end of this section you should be able to

• Use recursion to efficiently search a list.
• Demonstrate a solution to the Three Towers problem.

## Binary search

Searching a sorted list usually involves looking at each item. If the item being searched is not found, then the search can take a long time.

A binary search is a recursive algorithm used to efficiently search sorted lists. In each recursive step, about half the items are discarded as not being potential matches, so the search proceeds much faster.

A binary search begins by checking the middle element of the list. If the search key is found, the algorithm returns the matching location (base case). Otherwise, the search is repeated on approximately half the list. If the key is greater than the middle element, then the key must be on the right half, and vice versa. The process continues by checking the middle element of the remaining half of the list.

## Example 12.3

### Binary search

    """ Binary Search """

def binary_search(search_list, low, high, key):

# Check base case
if high > low:
mid = (high + low) // 2

# If element is present at the middle itself (base case)
if search_list[mid] == key:
return mid

# Recursive case: check which subarray must be checked
# Right subarray
elif key > search_list[mid]:
return binary_search(search_list, mid + 1, high, key)

# Left subarray
else:
return binary_search(search_list, low, mid - 1, key)

else:

# Test list
in_list = [1, 3, 13, 16, 19, 22, 27, 32, 48, 66, 78, 99, 111, 122]

# Call binary search function
print(binary_search(in_list, 0, len(in_list)-1, 48)) # Key exists at index 8

print(binary_search(in_list, 0, len(in_list)-1, 86)) # Key does not exist


The above code's output is:

    8


## Concepts in Practice

### Binary search

1.
Which list can be searched with the binary search algorithm?
1. [5, 2, 7, 1, 8]
2. [9, 8, 7, 6, 5]
3. [4, 5, 6, 7, 8]
2.
If the binary_search() function is called with low = 4, and high = 7, mid computes to _____.
1. 5
2. 6
3. 11
3.
How many calls to the binary_search() function occur in the animation?
1. 3
2. 4
3. 8
4.
How many calls to the binary_search() function occur in the code example when searching 86?
1. 4
2. 14

## Solving Three Towers

As discussed in an earlier section, the Three Towers problem can be solved using recursion. The solution depends on calling the solution to the next smaller problem twice. As shown in the code example below, the recursive solution can solve the problem for any number of rings.

## Example 12.4

### Solving N towers

The solution to Three Towers is simple with recursion. In the code below, rings are numbered from the top down. The smallest ring is 1, the next ring is 2, and when solving for three rings, the bottom ring is 3.

    """ Solving the towers problem recursively """

def three_towers(N, source_tower, dest_tower, temp_tower):
# Base case: simply move the single(bottom) ring from source to destination tower
if N==1:
print("Move ring 1 from tower", source_tower, "to tower", dest_tower)
return # Exit when the base case is reached

# Recursive case
# Call the smaller version of the problem:
# to move the N-1 stack to the middle tower
three_towers(N-1, source_tower, temp_tower, dest_tower)

# Move the N ring to the destination tower
print("Move ring", N, "from tower", source_tower, "to tower", dest_tower)

# Call the smaller version of the problem:
# to now move the N-1 stack from the middle tower
# to the destination
three_towers(N-1, temp_tower, dest_tower, source_tower)

# Test code
print("Solution for 3 rings:")
three_towers(3, 't1', 't3', 't2') # t1, t2, t3 are the towers


The above code's output is:

    Solution for 3 rings:
Move ring 1 from tower t1 to tower t3
Move ring 2 from tower t1 to tower t2
Move ring 1 from tower t3 to tower t2
Move ring 3 from tower t1 to tower t3
Move ring 1 from tower t2 to tower t1
Move ring 2 from tower t2 to tower t3
Move ring 1 from tower t1 to tower t3


## Concepts in Practice

### Solving Three Towers

5.
For four rings, how many total lines will be printed by three_towers()?
1. 7
2. 15
6.
Would an iterative solution to the Three Towers problem be more complex or less complex?
1. more complex
2. less complex

## Try It

### Coin combinations

Write a recursive function print_H_T() that produces all possible combinations of heads ("H") and tails ("T") for a given number of coin tosses.

Ex: For three coins, the program should print the output shown below.

    HHH
HHT
HTH
HTT
THH
THT
TTH
TTT


This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.