On this page:
1 Binary search
2 Euclid’s algorithm
8.6.0.14

Lab 12: Generative recursion 2

Remember to follow (and when necessary, adapt) the design recipe for each function. When you write a generative recursive function, you must provide a termination argument.

1 Binary search

Searching is a very common task: we might want to know how many times a given word occurs in a book, or find someone’s phone number in a contact list or phonebook. In Problem set 7: Lists, you implemented searching through a list of frequencies. In Problem set 10: Prefix trees, you implemented searching through a tree of letters. A list and a tree represent two different ways to decompose a search problem. Searching through a list can be slower than searching through a tree, because in a list, the target can be buried much farther from the root.

Binary search is a general and efficient search algorithm. It requires the data to be sorted, like the headwords in a dictionary. To look for a word in a dictionary using binary search, first we flip to the middle of the dictionary, and compare the word in the middle to the word we want. If they happen to be the same, then we’re lucky and done. If they’re different, then depending on their relative order, we can always throw away half of the dictionary. For instance, if we’re looking for “bro” and the middle of the dictionary is “law”, then we can throw away the second half of the dictionary, and continue with the middle of the first half.

In this section, you will implement binary search. The key is to decompose the problem of searching through a sorted list into the smaller problems of searching through its two halves.

Exercise 1. Let’s first practice the decomposition by hand. Finish the following tree on a piece of paper:

Each box contains a sorted list to search through.
  • If the list has an odd number of elements (say 9), then split it into two equally long halves (4 each), and leave the middle element.

  • If the list has an even number of elements (say 4), then split it into two equally long halves (2 each), and remove the first element from the right half to become the middle element.

  • Stop only when the list is empty. Any non-empty box, such as or even just , must be decomposed further.

Exercise 2.
; A SearchTree is one of:
; - (make-not-found)
; - (make-try SearchTree String SearchTree)
(define-struct not-found [])
(define-struct try [left middle right])
Define the SearchTree you just made as a constant. Call it neighbors, because it contains the names of Monroe County and its neighbors.

Exercise 3. Design a function search-tree-contains? that determines whether the given SearchTree contains the given string. For example, neighbors contains "Monroe" but not "Middlesex".

Instead of generative recursion, stick with structural recursion and follow the template for processing a SearchTree. Do not search through the entire tree; that’s way slower. Instead, assume that the tree is sorted. So, every time you come to a try, you can compare its middle against the given string (using string=? and string<?) to decide whether to go left, stop, or go right. The video above only makes 3 comparisons! In other words, never make both of the two recursive calls offered by the template.

The goal of the rest of this section is to generate a SearchTree from a sorted list of county names. The problem decomposition can use some helper functions.

Exercise 4. Design a function left-half that takes a non-empty list as input and returns its first half. If the input list has 9 elements, then the output list should be its first 4 elements. Don’t use cond; instead, use length and the following handy function from lecture:
; take : {X} NaturalNumber [ListOf X] -> [ListOf X]
; take the first that-many elements of the list
(check-expect (take 2 (list "almond" "pecan" "walnut" "pistachio"))
              (list "almond" "pecan"))
(define (take n l)
  (cond [(or (= n 0) (empty? l)) empty]
        [else (cons (first l) (take (- n 1) (rest l)))]))

Exercise 5. Design a function middle-element that takes a non-empty list as input and returns its middle element. If the input list has 4 elements, then the output should be its third element. Don’t use cond; instead, use length and the following handy function from lecture:
; drop : {X} NaturalNumber [ListOf X] -> [ListOf X]
; drop the first that-many elements of the list
(check-expect (drop 2 (list "almond" "pecan" "walnut" "pistachio"))
              (list "walnut" "pistachio"))
(define (drop n l)
  (cond [(or (= n 0) (empty? l)) l]
        [else (drop (- n 1) (rest l))]))

Exercise 6. Design a function right-half that takes a non-empty list as input and returns its second half without its middle element. If the input list has 9 elements, then the output list should be its last 4 elements. If the input list has 4 elements, then the output list should contain just its last element.

Exercise 7. Design a function generate-search-tree that decomposes a given [ListOf String] into a SearchTree. Follow the decomposition strategy in Exercise 1.

Hint: Use generative recursion. Again, remember to make your function terminate, and explain how by writing a termination argument. Use left-half, middle-element, and right-half.

Exercise 8. Download the text file counties.txt, which contains an alphabetical list of Indiana county names. Create a [ListOf String] from this downloaded file, using the function read-lines provided by the 2htdp/batch-io library. Turn the [ListOf String] into a SearchTree, using the generate-search-tree function you just designed. Finally, use search-tree-contains? to answer the following questions:
  • Is Monroe an Indiana county name?

  • Is Middlesex an Indiana county name?

Challenge. There’s a bug! Decatur is an Indiana county name, and it is in the text file, but search-tree-contains? fails to find it. What’s causing this bug? How can you fix it without reordering the names?

2 Euclid’s algorithm

The greatest common divisor (GCD) of two numbers is the largest number that divides them both. For example, the GCD of 115 and 50 is 5, because 5 divides both 115 and 50 evenly, and no number greater than 5 divides both 115 and 50 evenly. In this section, you’ll use generative recursion to find the GCD of two numbers, without using any built-in function for doing so. You will implement Euclid’s algorithm, which is more than 2000 years old!

This algorithm decomposes the problem by dividing the two numbers and taking the remainder. For example:
  • The problem of finding the GCD of 115 and 50 decomposes to the problem of finding the GCD of 50 and 15, because the remainder of dividing 115 by 50 is 15.

  • Then, the problem of finding the GCD of 50 and 15 decomposes to the problem of finding the GCD of 15 and 5, because the remainder of dividing 50 by 15 is 5.

  • Further following the same pattern, the problem of finding the GCD of 15 and 5 decomposes to the problem of finding the GCD of 5 and 0, because the remainder of dividing 15 by 5 is 0.

  • Finally, we cannot divide 5 by 0, but the GCD of any number and 0 is that number, so we know that the GCD of 5 and 0 is 5, and that is the base case where our decomposition terminates.

Because our decomposition of the GCD problem divides the first number by the second number, we call the first number the numerator and the second number the denominator. We assume that both numbers are natural numbers, but do not follow the template for processing a natural number because it leads to the wrong algorithm that is too slow.

Exercise 9. Design a function generate-euclid-tree that takes two natural numbers as input, a numerator and a denominator, and decomposes the GCD problem into a EuclidTree defined below:
; A EuclidTree is one of:
; - (make-d=0 Number)
; - (make-d<>0 Number EuclidTree)
(define-struct d=0 [num])
(define-struct d<>0 [quotient div])
; *Interpretation*: in the d<>0 case, div is the EuclidTree
; after dividing the numerator by the denominator
In a EuclidTree, each d<>0 represents a division and records its resulting quotient. At the base of every EuclidTree is a d=0, which represents the denominator reaching zero and records the numerator.
(check-expect (generate-euclid-tree 5 0)
              (make-d=0 5))
(check-expect (generate-euclid-tree 15 5)
              (make-d<>0 3 (make-d=0 5)))
(check-expect (generate-euclid-tree 115 50)
              (make-d<>0 2 (make-d<>0 3 (make-d<>0 3 (make-d=0 5)))))
Use the built-in functions quotient and remainder in your definition. (Do you need to provide a termination argument?)

Exercise 10. Now that we have decomposed the GCD problem, we can read off the answer by processing the decomposition.

Design a function euclid-tree-gcd that takes a EuclidTree and returns the GCD resulting from the divisions. The GCD is the d=0-num stored deep at the base in the EuclidTree. For example, the following test says that the GCD of 115 and 50 is 5:
(check-expect
 (euclid-tree-gcd (make-d<>0 2 (make-d<>0 3 (make-d<>0 3 (make-d=0 5)))))
 5)
Follow the template for processing a EuclidTree. (Do you need to provide a termination argument?)

Exercise 11. To represent Euclid’s algorithm by a picture, design a function euclid-tree-rectangle that takes a EuclidTree and returns an image whose width is the numerator and whose height is the denominator. The image should look like a rectangle made of a nest of squares. For example, the picture to the right represents computing the GCD of 115 and 50. It is 115 pixels wide and 50 pixels tall. It contains 2 large squares, of size 50, because dividing 115 by 50 gives the quotient 2. It also contains 3 medium squares, of size 15, because dividing 50 by 15 gives the quotient 3. Finally it contains 3 small squares, of size 5, because dividing 15 by 5 gives the quotient 3.
(check-expect
 (euclid-tree-rectangle
  (make-d=0 5))
 (rectangle 5 0 "outline" "purple"))
(check-expect
 (euclid-tree-rectangle
  (make-d<>0 3 (make-d<>0 3 (make-d=0 5))))
 (beside (above (square 5 "outline" "purple")
                (square 5 "outline" "purple")
                (square 5 "outline" "purple"))
         (square 15 "outline" "purple")
         (square 15 "outline" "purple")
         (square 15 "outline" "purple")))
(check-expect
 (euclid-tree-rectangle
  (make-d<>0 2 (make-d<>0 3 (make-d<>0 3 (make-d=0 5)))))
 (beside (above (beside (square 5 "outline" "purple")
                        (square 5 "outline" "purple")
                        (square 5 "outline" "purple"))
                (square 15 "outline" "purple")
                (square 15 "outline" "purple")
                (square 15 "outline" "purple"))
         (square 50 "outline" "purple")
         (square 50 "outline" "purple")))
Follow the template for processing a EuclidTree. (Do you need to provide a termination argument?) Use the functions rectangle (or square), image-height (or image-width), beside (or above), and rotate provided by the 2htdp/image library.

Challenge. Given two numbers a and b, we can now compute their GCD by
(euclid-tree-gcd (generate-euclid-tree a b))
and visualize the process by
(euclid-tree-rectangle (generate-euclid-tree a b))
Moreover, it turns out that we can always find integers x and y such that
(+ (* a x) (* b y))
is equal to the GCD of a and b. For example, if a = 115 and b = 50 then we can find x = -3 and y = 7 such that
(+ (* a x) (* b y)) = (+ (* 115 -3) (* 50 7))
is equal to the GCD 5 of a and b. Computing this pair of coefficients x and y is one of the foundations of modern cryptography.

Design a function that takes a EuclidTree (generate-euclid-tree a b) and finds a Posn (make-posn x y) such that
(+ (* a x) (* b y))
is equal to the GCD of a and b. Hint: Follow the template for processing a EuclidTree.