12.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:
# Key not found (other base case)
return "Not found"
# 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
Not found
Concepts in Practice
Binary search
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
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