#set document(title: "12.5 Using recursion to solve problems", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 12.5#h(0.6em)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. #examplebox("Example 1")[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 ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Binary search] #link("https://www.openstax.org/r/binary-search")[Binary search; ch 12, video 8] ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[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. #examplebox("Example 2")[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 ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Solving Three Towers] ] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[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 \# Test code print\_H\_T(3) ]