Skip to ContentGo to accessibility pageKeyboard shortcuts menu
OpenStax Logo
Introduction to Python Programming

12.5 Using 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:
        # 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
    

Checkpoint

Binary search

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
    
Citation/Attribution

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.

Attribution information
  • If you are redistributing all or part of this book in a print format, then you must include on every physical page the following attribution:
    Access for free at https://openstax.org/books/introduction-python-programming/pages/1-introduction
  • If you are redistributing all or part of this book in a digital format, then you must include on every digital page view the following attribution:
    Access for free at https://openstax.org/books/introduction-python-programming/pages/1-introduction
Citation information

© Feb 26, 2024 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.