Programming fundamentalsLesson 2 of 2 in the course Recursion

Recursive Binary Search, Three Towers, and Coin-Toss Sequences

5 flashcards · 5 quiz questions · 5 match pairs · 4 fill-in sentences · English

Save course
Lesson progress
0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

Recursion can make problems easier to solve by reducing them to smaller versions of the same problem. This lesson explores how recursion searches a sorted list, solves the Three Towers puzzle, and generates every possible sequence of coin tosses.

A linear search may inspect every item in a list. Binary search is faster for a sorted list because each comparison discards about half of the remaining items.

All flashcards

What is binary search?
A search algorithm for sorted data that checks the middle item and continues in the half that could contain the key.
What are the two base cases in recursive binary search?
The key is found at the midpoint, or the search range becomes empty, indicating the key is absent.
What is the recursive plan for moving NN rings in the Three Towers problem?
Move N−1N-1 rings to the temporary tower, move the largest ring to the destination, then move the smaller stack onto the destination.
How many moves does the optimal Three Towers solution require for NN rings?
2N−12^N - 1 moves, because the smaller stack must be moved twice around the move of the largest ring.
How does recursive coin-sequence generation create all outcomes?
It makes one recursive call adding `H` and another adding `T`; when no tosses remain, it prints the completed sequence.

Quiz questions

  1. What key property must a list have for binary search to work correctly?Answer: The list must be sorted.
  2. After binary search compares the middle item with a key and they differ, why can it discard half the current range?Answer: Sorted order shows which half could still contain the key.
  3. In binary search, what does the condition `low > high` indicate?Answer: The search range is empty, so no remaining item can match the key.
  4. In the Three Towers solution, what happens immediately after the top N−1N-1 rings are moved to the temporary tower?Answer: The largest ring is moved from the source tower to the destination tower.
  5. How many possible sequences can be made from four coin tosses?Answer: 24=162^4 = 16

Based on Introduction to Python Programming by Udayan Das, Aubrey Lawson, Chris Mayfield, Narges Norouzi (OpenStax), licensed CC BY 4.0. Adapted into a summary, flashcards and quizzes.

More in Programming fundamentals

All Programming fundamentals lessons
Programming fundamentalsTracing Conditional and Function-Call Control Flow5 flashcards · 5 quiz questions · 4 gamesPlay free →Programming fundamentalsWhile Loops: Conditions, Counters, and Input-Controlled Repetition5 flashcards · 5 quiz questions · 4 gamesPlay free →Programming fundamentalsVariable Scope: Global and Local Variables in Python5 flashcards · 5 quiz questions · 4 gamesPlay free →Programming fundamentalsPython Function Arguments, Defaults, and PEP 8 Spacing5 flashcards · 5 quiz questions · 4 gamesPlay free →Programming fundamentalsRecursive Cases and Base Cases in Elementary Math Functions5 flashcards · 5 quiz questions · 4 gamesPlay free →Programming fundamentalsPython's Origins, Design Goals, and Popularity Measures5 flashcards · 5 quiz questions · 4 gamesPlay free →