Assignment 18
Due Date Mon 3/27 at 11:59pm
Possible Points 41
Purpose To use generative recursion to solve complex problems.
Graded Exercises
The following two functions use generative recursion. In generative recursive code, termination is no longer obvious. Above functions that use generative recursion, write a termination statement below the purpose statement. A termination statement is a comment that begins with "Termination:" and then briefly (1-2 sentences) explains why this function terminates.
Exercise 1 Design the function slice which takes a list and a positive integer i and slices the list into segments of length i (with the last one possibly being shorter). For example, (slice '(a b c d e) 2) should return '((a b) (c d) (e)). Solve this problem with generative recursion.
(define-struct vector [length lookup]) ; A Vector is a (make-vector Natural [Natural -> Number]) ; and represents indexed numbers (where indices go from 0 up to and not including the length)
Exercise 2 Design the function find-root which takes a monotonically increasing vector and outputs the index that corresponds to the leftmost 0. If there is no such index, output #false. Use binary search to make this efficient.