#lang racket (require csc151) (require racket/undefined) (require rackunit) ;; CSC 151-01 (Fall 2021) ;; Lab: Recursive Design ;; Authors: YOUR NAMES HERE ;; Date: THE DATE HERE ;; Acknowledgements: ;; ACKNOWLEDGEMENTS HERE #| In the prior lab, you practiced reading recursive procedures. Today, you will explore the construction of some recursive procedures. |# ; +---------------+-------------------------------------------------- ; | Supplied code | ; +---------------+ ;;; (sum numbers) -> number? ;;; numbers : listof number? ;;; Add all the numbers in a list together. (define sum (lambda (numbers) (if (null? numbers) 0 (+ (car numbers) (sum (cdr numbers)))))) ;;; (select-numbers values) -> listof? number ;;; values : list? ;;; Select all the numbers in values, putting them into a new list. (define select-numbers (lambda (values) (cond [(null? values) null] [(not (number? (car values))) (select-numbers (cdr values))] [else (cons (car values) (select-numbers (cdr values)))]))) ;;; (count-value value values) -> integer? ;;; value : any? ;;; values : list? ;;; Count how many times value appears in values. (define count-value (lambda (value values) (cond [(null? values) 0] [(equal? value (car values)) (+ 1 (count-value value (cdr values)))] [else (count-value value (cdr values))]))) ;;; (largest numbers) -> integer? ;;; numbers : listof integer? ;;; Finds the largest number in a list (define largest (lambda (numbers) (if (null? (cdr numbers)) (car numbers) (max (car numbers) (largest (cdr numbers)))))) #| A |# ; +---------------------------------------------+-------------------- ; | Exercise 1: Exploring recursive definitions | ; +---------------------------------------------+ #| As you may have determined in your initial explorations with recursion, a typical recursive procedure has three parts: (1) a *base case*, in which we use a *base case test* to determine whether the input is simple enough and, if so, return an appropriate *base case value*; (2) a *recursive call*, in which we call the same procedure again, albeit on parameters we have *simplified*, and, in most cases, a (3) *post-recursion step*, in which we do something with the recursive result. Some procedures may have different recursive calls or post-recursion steps. For example, we might do something different for even-length and odd-length lists. Review the procedures above and, for each, note the various parts. If a procedure has multiple recursive calls, separate them out in the explanation. a. sum base-case-test: base-case-value: parameter simplification: recursive call: post-recursion step: b. select-numbers base-case-test: base-case-value: parameter simplification: recursive call: post-recursion step: c. count-value base-case-test: base-case-value: parameter simplification: recursive call: post-recursion step: d. largest base-case-test: base-case-value: parameter simplification: recursive call: post-recursion step: |# ; +-----------------------------+------------------------------------ ; | Exercise 2: Counting values | ; +-----------------------------+ #| Suppose the `length` procedure, which computes the length of a list, were not defined. We could define it by recursing through the list, counting 1 for each value in the list. In some sense, this is much like the definition `of` sum, except that we use the value 1 rather than the value of each element. |# #| a. Using this idea, write a *recursive* procedure, `(list-length lst)` that finds the length of a list. You may not use `length` in defining `list-length`. |# (define list-length (lambda (lst) 0)) #| b. Write tests to check your answer on a few examples: the empty list, the list of values you created, and a few more lists of your choice. |# #| B |# ; +--------------------------------+--------------------------------- ; | Exercise 3: Computing products | ; +--------------------------------+ #| Write a recursive procedure, `(product nums)`, that computes the product of a list of numbers. You should feel free to use `sum` as a template for `product`. However, you should think carefully about the base-case test and the base-case value. |# (define product (lambda (nums) -1)) ; +--------------------------------------+--------------------------- ; | Exercise 4: Counting with predicates | ; +--------------------------------------+ #| The `length` procedure counts all the values in a list. The `count-value` procedure counts how many time a supplied value appears in a list. What if we want something in between the two: Rather than counting all the values, we only want to count some of them, and rather than counting a single value, we want to count all values matching a particular criterion? (You may think of this as `tally`.) |# #| Document, write tests for, and implement a recursive procedure, `(tally-odd numbers)` that, given a list of integers, counts how many are odd. Note: You should not call list-length, length, filter, tally, or count-value in your solution. Instead, use the ideas behind some or all of these functions in crafting your own recursive solution. |# (define tally-odd (lambda (numbers) -1)) #| A |# ; +----------------------------+------------------------------------- ; | Exercise 5: Longer strings | ; +----------------------------+ #| Document, write tests for, and implement a recursive procedure, `(longest-string words)`, that finds the longest string in a list of strings. If multiple strings have the same length, you can return any of the longest strings.) |# (define longest-string (lambda (words) "")) #| B |# ; +-------------------------------+---------------------------------- ; | Exercise 6: What comes first? | ; +-------------------------------+ #| Document, write tests for, and implement a recursive procedure, `(alphabetically-first words)`, that finds the alphabetically first string in a list of strings. You can use `string-ci<=?` to compare any two strings for alphabetical order. You may not use `sort` to solve this problem. |# (define alphabetically-first (lambda (words) "")) #| AB |# ; +---------------------------+-------------------------------------- ; | For those with extra time | ; +---------------------------+ #| If you find that you have extra time and want to further explore some of these issues, consider implementing any of the following procedures. |# ; +--------------------------+--------------------------------------- ; | Extra 1: Skipping values | ; +--------------------------+ #| Document, write tests for, and write a procedure, `(find-first-skip lst)` that takes a list of symbols as a parameter and returns the index of the first instance of the symbol `'skip` in `lst`, if `skip` appears in `lst`, and false otherwise. > (find-first-skip (list 'hop 'skip 'and 'jump)) 1 > (find-first-skip (list 'skip 'hop 'jump 'skip 'and 'skip 'again)) 0 > (find-first-skip (list 'hop 'to 'work 'jump 'to 'school 'but 'never 'skip 'class)) 8 |# (define find-first-skip (lambda (lst) #f)) ; +--------------------------+--------------------------------------- ; | Extra 2: Finding indices | ; +--------------------------+ #| Document, write tests for, and implement a recursive procedure, `(find-index val lst)`, that takes a value and a list of values as its parameters and returns the index of the first instance of val in lst, if the value appears in the list. If the value does not appear, find-index should return #f. |# (define find-index (lambda (val lst) #f)) ; +-------------------------+---------------------------------------- ; | Extra 3: Riffling lists | ; +-------------------------+ #| Document, write tests for, and implement a recursive proceure, (riffle first second) that produces a new list containing alternating elements from the lists first and second. If one list runs out before the other, then the remaining elements should appear at the end of the new list. > (riffle (list 'a 'b 'c) (list 'x 'y 'z)) (a x b y c z) > (riffle (list 'a 'b 'c) (range 0 10)) (a 0 b 1 c 2 3 4 5 6 7 8 9) |# (define riffle (lambda (first second) null))