15 Working with more complicated recursive procedures
(7 activities)
15.1 Quiz: "Starting to think recursively"(1 step)
15.1.1 (Student Assessment) Analyze a recursion, then invent some.
1. Give a good comment for the following procedure. 
(define (mystery sent)
  (if (empty? sent)
      sent
      (sentence (first sent) (mystery (butfirst sent))) ) )
2.Assume that you are working with a "celebrity" program that someone else wrote. This package gives you accessors (or selectors) to work with a "celebrity". You won't change (or even look at) those procedures, but will use them. Some of these accessors include
  • name, which takes a single celebrity and returns the name as a single word. For example, if you have stored a celebrity in the variable cel, 
             (name cel)
    might return the word Joe.
  • hair-color which takes a celebrity and returns one of the words blond, brown, black, or red
  • the procedure movies, which returns a sentence of movies that the celebrity has been in
  • and many other procedures
Only by using the accessors can the information about a celebrity be pulled out. Write a recursive procedure find-michael which takes a sentence of celebrities and returns a sentence of celebrities who have the name of michael. The procedure should return an empty sentence if there are no such named celebrities.
3.For this question, assume you are still using the celebrity package discussed earlier. Write a recursive procedure gather-with-hair-color which takes two arguments: first, a word specifying a hair-color; second, a sentence of celebrities. The procedure should return a sentence containing the celebrities that have a hair color equal to the first argument. If there are no such celebrities, the procedure should return the empty list.
15.2 Use a new tool.(1 step)
15.2.1 (Display page) Try the Replacement Modeler.
Now you get to see a neat tool in STk. It's called the Replacement Modeler, and it "slows down", or "steps", the process of evaluation. Here is how to use it.
  1. Pick an expression whose evaluation you would like to examine in detail. Type 
        (model  your_expression )
    (don't quote the expression). Then press ENTER. A window will appear with your expression in it.
  2. Hit RETURN (not ENTER) to advance through one step of the evaluation. This step will either be to evaluate the arguments of a procedure call, or to substitute argument values into the body of a procedure, or to evaluate part of a cond or an if. The result will appear on the next line of the display.
You can keep hitting RETURN until you reach the final answer or an error. The Modeler can be a really good way to locate bugs in your program. For example, suppose you type
(model (+ 3 (* 4 5) 6 (* 7 (+ 8 9)) 10))
into stk. Another window will pop up with the expression that you gave to the model command. Each time you press RETURN the inner portions of the expression will be evaluated and inserted into the full expression, simplifying it. One RETURN will give
(+ 3 20 6 119 10)
and another RETURN
158
If you want to focus on a particular sub-part of the expression, you can use your mouse to select that sub-part. Hitting RETURN when a sub-part of the expression is highlighted in this way will cause only that highlighted part to be evaluated and substituted. For instance, if you highlight the (* 4 5) in the original expression at the top-line of the replacement modeler window, you will see a second line of
(+ 3 20 6 (* 7 (+ 8 9)) 10)
Note that the (* 7 (+ 8 9)) was not changed. You can use this to focus in more carefully on areas of interest. Be sure to try the replacement modeler with calls to recursive functions. Remember, when you call model, don't quote the argument! Hopefully, this will seem weird to you -- i.e., why isn't the argument evaluated before model sees it? However, you can consider model to be a special form like quote, and the argument will not be evaluated.
15.3 Work with a recursive version of day-span.(4 steps)
15.3.1 (Evidence) Here is code for a recursive version of day-span.
If you would like this to open in another window, click here. 
; Appendix C
; Recursive computation of the difference between dates

; Return the number of days spanned by earlier-date
; and later-date. 
; Earlier-date and later-date both represent dates in 2002, 
; with earlier-date being the earlier of the two.
(define (day-span earlier-date later-date)
  (cond
    ((same-month? earlier-date later-date)
     (same-month-span earlier-date later-date) )
    ((consecutive-months? earlier-date later-date)
     (consec-months-span earlier-date later-date) )
    (else
     (general-day-span earlier-date later-date) ) ) )

; Access functions for the components of a date.
(define (month-name date) (first date))
(define (date-in-month date) (first (butfirst date)))

; Return true if date1 and date2 are dates in the same month, and
; false otherwise. Date1 and date2 both represent dates in 2002.
(define (same-month? date1 date2)
  (equal? (month-name date1) (month-name date2)))

; Return the number of the month with the given name.
(define (month-number month-name)
  (cond
    ((equal? month-name 'january) 1)
    ((equal? month-name 'february) 2)
    ((equal? month-name 'march) 3)
    ((equal? month-name 'april) 4)
    ((equal? month-name 'may) 5)
    ((equal? month-name 'june) 6)
    ((equal? month-name 'july) 7)
    ((equal? month-name 'august) 8)
    ((equal? month-name 'september) 9)
    ((equal? month-name 'october) 10)
    ((equal? month-name 'november) 11)
    ((equal? month-name 'december) 12) ) )

; Return true if date1 is in the month that immediately precedes the 
; month date2 is in, and false otherwise. 
; Date1 and date2 both represent dates in 2002.
(define (consecutive-months? date1 date2)
  (= 
    (month-number (month-name date2))
    (+ 1 (month-number (month-name date1))) ) )

; Return the difference in days between earlier-date and later-date, 
; which both represent dates in the same month of 2002.
(define (same-month-span earlier-date later-date)
  (+ 1
    (- (date-in-month later-date) (date-in-month earlier-date)) ) )

; Return the number of days in the month named month-name.
(define (days-in-month month-name)
  (cond
    ((equal? month-name 'january) 31)
    ((equal? month-name 'february) 28)
    ((equal? month-name 'march) 31)
    ((equal? month-name 'april) 30)
    ((equal? month-name 'may) 31)
    ((equal? month-name 'june) 30)
    ((equal? month-name 'july) 31)
    ((equal? month-name 'august) 31)
    ((equal? month-name 'september) 30)
    ((equal? month-name 'october) 31)
    ((equal? month-name 'november) 30)
    ((equal? month-name 'december) 31) ) )

; Return the number of days remaining in the month of the given date, 
; including the current day. Date represents a date in 2002.
(define (days-remaining date)
  (+ 1 (- (days-in-month (month-name date)) (date-in-month date))) )

; Return the difference in days between earlier-date and later-date, 
; which represent dates in consecutive months of 2002.
(define (consec-months-span earlier-date later-date)
  (+ (days-remaining earlier-date) (date-in-month later-date)) )

; Return the name of the month with the given number.
; 1 means January, 2 means February, and so on.
(define (name-of month-number)
  (item 
    month-number
    '(january february march april may june
      july august september october november december) ) )

; Return the sum of days in the months represented by the range 
;    first-month through last-month.
; First-month and last-month are integers; 1 represents January,
; 2 February, and so on.
; This procedure uses recursion.
(define (day-sum first-month last-month)
  (if (> first-month last-month) 0
    (+ 
      (days-in-month (name-of first-month))
      (day-sum (+ first-month 1) last-month)) ) )

; Return the number of the month that immediately precedes the month
; of the given date.  1 represents January, 2 February, and so on.
(define (prev-month-number date)
  (- (month-number (month-name date)) 1) )

; Return the number of the month that immediately follows the month
; of the given date.  1 represents January, 2 February, and so on.
(define (next-month-number date)
  (+ (month-number (month-name date)) 1) )

; Return the difference in days between earlier-date and later-date, 
; which represent dates neither in the same month nor in consecutive months.
(define (general-day-span earlier-date later-date)
  (+
    (days-remaining earlier-date)
    (day-sum
      (next-month-number earlier-date)
      (prev-month-number later-date) )
    (date-in-month later-date) ) )
15.3.2 (Brainstorm) Find a bug.
Your helper monkey accidentally changes a single symbol in one of the lines of the recursive day-span program, with the result that day-span's return values are now too large:
call to day-span returned value
(day-span '(january 1) '(december 31)) 396
(day-span '(february 1) '(december 31)) 362
(day-span '(january 1) '(november 30)) 365
What symbol could your partner have changed to produce this behavior?
15.3.3 (Brainstorm) How did you find it?
What technique did you use to find the bug? Did you guess wildly? Did you reason it out? Give us some details.
15.3.4 (Brainstorm) Can day-span be simplified?
Are the first two cases in day-span still necessary? That is, can day-span now be coded merely as a call to general-day-span? Explain why or why not.
15.4 Design some more recursive procedures.(2 steps)
15.4.1 (WebScheme) Write down-to-0.

Write down-to-0

Write a procedure named down-to-0 that, given an integer n as argument, returns the sentence (n n-1 ... 0) (Do this without using reverse. ) If n is negative, down-to-0 should return the empty sentence.
your procedure run tests result
;; Return a sentence that, given an integer n, 
 ;; contains the integers from n down to 0: (n n-1 ... 0) 
 (define (down-to-0 n) 
   (if   
      
       ) )
 Status icon
down-to-0 call desired result your result
(down-to-0 -3) ( ) ????
(down-to-0 0) (0) ????
(down-to-0 3) (3 2 1 0) ????
If you miss any of these, put an entry in your Extra Brain explaining the reason you missed it.
15.4.2 (WebScheme) Write the remove procedure.

Write remove

Write a procedure named remove that, given a character char and a word wd as arguments, returns the result of removing all occurrences of char from wd.
your procedure run tests result
;; Return the result of removing all occurrences of the given character 
 ;; from the given word. 
 (define (remove char wd) 
     
 )
 Status icon
remove call desired result your result
(remove 'a 'radar) rdr ????
(remove 'a 'xyz) xyz ????
(remove 'a 'aaaa) "" ????
(remove 'a 'pear) per ????
If you miss any of these, put an entry in your Extra Brain explaining the reason you missed it.
15.5 Design a recursion using simple cases and clones.(4 steps)
15.5.1 (Display page) Here's another way to approach the design of recursive procedures.
So far, we have seen how to design recursive procedures by doing the following:
  1. designing a procedure to handle an argument of size 0, another procedure to handle an argument of size 1, a third to handle an argument of size 2, and so on;
  2. rewriting those procedures if necessary to maximize their similarity;
  3. designing one or more recursive calls that match the pattern of the rewritten procedures;
  4. fixing up the base case(s) to work correctly with the recursive calls we've just designed.
Many programmers prefer to work in the opposite sequence. They look for all the cases that are easy to solve—for example, those involving small numbers or small sentences or words—and use these as their base cases. For the copies procedure you saw earlier, they might start coding with three easy cases: 
; Return a sentence that contains n copies of the word x.
(define (copies n x)
  (cond
    ((= n 0) '( ))
    ((= n 1) (sentence x))
    ((= n 2) (sentence x x))
    ; the remainder of the procedure is yet to fill in.
))
Then they consider a big argument, and say, "Suppose I had a clone—a copy of myself—that would give me a sentence of any number of copies of my x, except that the number of copies it would give me has to be smaller than my n. How would I use the clone's answer to produce my own answer?" They would continue by asking the clone for n-1 copies of x; then they would add one more copy and return the result.
15.5.2 (Brainstorm) Try out this approach.
We will now try to apply this use-a-clone approach to the problem of writing a procedure sent-max that returns the largest value in its argument, a nonempty sentence of numbers. Suppose you are sent-max, and someone gives you a sentence that contains five numbers. You want to prepare an argument to give your clone; he or she will return to you the maximum value in whatever sentence you provide, as long as it's a simpler sentence than the one you were given. Which of the following simpler sentences should you give your clone?
  1. butfirst of the sentence you were given (its last four numbers);
  2. some other sentence that contains four numbers;
  3. a sentence with five numbers that results from subtracting 1 from each of the numbers in your sentence (e.g. if the sentence you were given was (3 -2 7 -4 5), you would give the clone the sentence (2 -3 6 -5 4).
Explain your answer by saying how you would use the result that the clone returns to you.
15.5.3 (WebScheme) Write a recursive predicate.

Write two versions of all-odd?

Design two different recursive versions of a procedure named all-odd? that, given a nonempty sentence of numbers, returns true if all the numbers in the sentence are odd and returns false otherwise. The first of your two versions should use if or cond without using and or or ; the other should do just the opposite. Click on the pointer to run some tests.
your procedures run tests result
 ;; Return true if all the numbers in the given sentence are odd. 
 ;; Return false otherwise. 
 ;; The argument sentence contains at least one number. 
 ;;  Do not use 'and' or 'or' in this solution. 
  ;;  all-odd-1 is the first version: 
 (define (all-odd-1? sent) 
     
 )
 Status icon
 ;;  all-odd-2 is the second version: 
  ;;  Do not use 'if' or 'cond' in this solution. 
 (define (all-odd-2? sent) 
     
 )
 Status icon
argument interval desired result your result from all-odd-1? your result from all-odd-2?
(2 4 -16) #f ???? ????
(5 -3 17) #t ???? ????
(5) #t ???? ????
(5 -43 20) #f ???? ????
If you miss any of these, put an entry in your Extra Brain explaining the reason you missed it.
15.5.4 (Brainstorm) What should all-odd? return for an empty argument?
It's not always clear what a recursive procedure should return for an argument like the empty sentence or word. Suppose your version of all-odd? had to deal with the possibility of an empty argument. What should (all-odd? '( )) return, and why? (If you are among the first to do this problem, be sure to return later to check the answers of your classmates.)
15.6 Design recursions that examine more than one word in a sentence at a time.(6 steps)
15.6.1 (Display page) Consider the letter-pairs example from the book.
Simply Scheme describes the procedure letter-pairs; given a word, letter-pairs returns a sentence that contains all pairs of consecutive letters in the word. For example, (letter-pairs 'george) returns (ge eo or rg ge). Here's their code. 
(define (letter-pairs wd)
  (if (<= (count wd) 1)
    '( )
    (sentence 
      (first-two wd) 
      (letter-pairs (butfirst wd)) ) ) )

; Helper procedure:
; Return a sentence that contains the first two letters
; of the given word (which must contain at least two words).
(define (first-two wd)
  (word (first wd) (first (butfirst wd))) )
The interesting thing about this example is not the recursive call, in which the argument is (butfirst wd) as in many of the other examples. It's the base case, which tests for a word with 0 or 1 character rather than just an empty word. The reason for this base case is to protect the call to first-two, which is going to use the second character in its argument word. If the procedure were coded as 
(define (letter-pairs wd)
  (if (empty? wd)
    '( )
    (sentence 
      (first-two wd) 
      (letter-pairs (butfirst wd)) ) ) )
a crash in first-two would result.
15.6.2 (Display page) Work with procedures that remove duplicate words from a sentence.
The next few steps involve procedures that return the result of removing duplicate words from their sentence arguments.
15.6.3 (Display page) Write dupls-removed.
Write a procedure named dupls-removed that, given a sentence as argument, returns the result of removing duplicate words from the sentence. (The member? procedure will be useful.) Put the procedure into a file named dupls-removed.scm. Test your procedure on the following examples: 
expression                           value to return
(dupls-removed '(a b c))             (a b c)
(dupls-removed '(a b c a d e b))     (c a d e b)
15.6.4 (Brainstorm) Analyze dupls-removed.
Suppose that your dupls-removed procedure (assuming it works correctly) were given a sentence containing a single A, two B's, and a single C, and it returned the sentence (A B C). What are all possibilities for the argument sentence that would produce this result? Briefly explain your answer.
15.6.5 (Brainstorm) Analyze, then fix a buggy adj-dupls-removed procedure
Consider the procedure adj-dupls-removed given below. Given a sentence as argument, it is supposed to return the result of removing all but the last of any sequence of duplicate adjacent elements. For example, 
(adj-dupls-removed '(A B B C D D D E))
should return (A B C D E). 
(define (adj-dupls-removed sent)
  (cond
    ((empty? sent) '( ))
    ((equal? (first sent) (first (butfirst sent)))
     (adj-dupls-removed (butfirst (butfirst sent))) )
    ((empty? (butfirst sent)) sent)
    (else 
     (se 
       (first sent) 
       (adj-dupls-removed (bf sent)) ) ) ) )
Describe, as completely as possible, the set of arguments for which it does not perform as specified. Then fix adj-dupls-removed.
15.6.6 (Display page) Design is-sorted?.
Write and test a procedure named is-sorted? that, given a sentence of numbers, returns true if they are sorted and false otherwise. A sentence is sorted when its first word is less than or equal to its second, which is less than or equal to its third, and so on. An empty sentence is also sorted. Put your procedure into a file named utils.scm. You will occasionally be using util.scm in later homework problems -- for instance, where you need to know whether a sentence is sorted for some sub-part of the problem. You will submit utils.scm for this sessions homework as well.
15.7 Homework(1 step)
15.7.1 (Display page) Do the following for homework.

Homework 8

  1. Go back to the last homework and make two thoughtful comments on other people's posts.

  2. Complete the files dupls-removed.scm and utils.scm (which will contain the procedures dupls-removed and is-sorted? respectively). Submit these files as hwk8 in the usual way. You don't need to submit test cases, but be sure to give a good comment before the top of each procedure!

  3. Read "Roman Numerals Case Study" in the reader.