Class 18: Recursion with Lists (2)

Held: Tuesday, 18 February 2003

Summary: Today we continue our exploration of recursion over lists.

Related Pages:

• EBoard.
• Reading on Recursion.
• Lab on List Recursion.

Assignments

• Read Recursion with Natural Numbers.

Notes:

• To make the <Delete> key delete forward, uncheck Edit->Preferences->Editing->General->Map delete to backspace.
• I've made lab writeup 2 optional. It replaces an undone writeup or provides a modicum of extra credit on your writeup grade.
• I've made some modifications to the list of topics to give you some more time to explore recursion.
• I'm in the midst of grading lab writeup 1. If you'd like to see what I was thinking when grading it, take a look at my notes on the writeups. (We may also discuss these at the beginning of class.)

Tallying Skips

• Here's one way to tally the skips in a list
  • If the list is empty, there are no skips.
  • If the first element of the list is skip, add 1 to the number of skips remaining in the list.
  • Otherwise, count the number of skips remaining in the list.
• Here's that strategy in code.

  (define tally-skips
    (lambda (lst)
      (cond
        ((null? lst) 0)
        ((eq? (car lst) 'skip) 
         (+ 1 (tally-skips (cdr lst))))
        (else (tally-skips (cdr lst))))))
  

• Let's watch it in action

  (tally-skips (list 'hop 'skip 'jump 'and 'skip 'again))
  => (tally-skips (list 'skip 'jump 'and 'skip 'again))
  => (+ 1 (tally-skips (list 'jump 'and 'skip 'again)))
  => (+ 1 (tally-skips (list 'and 'skip 'again)))
  => (+ 1 (tally-skips (list 'skip 'again)))
  => (+ 1 (+ 1 (tally-skips (list 'again))))
  => (+ 1 (+ 1 (tally-skips (list))))
  => (+ 1 (+ 1 0))
  => (+ 1 1)
  => 2
  

• One might also decide to add an extra parameter, tally, that keeps track of each skip seen.
  • If there are no values left in the list, use tally
  • If the first value is skip, add 1 to tally and continue with the remaining values.
  • Otherwise, just use the same tally and continue with the remaining values.
• In code,

  (define tally-skips-helper
    (lambda (lst tally)
      (cond
        ((null? lst) tally)
        ((eq? (car lst) 'skip)
         (tally-skips-helper (cdr lst) (+ 1 tally)))
        (else (tally-skips-helper (cdr lst) tally)))))
  

• Let's watch it in action

  (tally-skips-helper (list 'hop 'skip 'jump 'and 'skip 'again) 0)
  => (tally-skips-helper (list 'skip 'jump 'and 'skip 'again) 0)
  => (tally-skips-helper (list 'jump 'and 'skip 'again) 1)
  => (tally-skips-helper (list 'and 'skip 'again) 1)
  => (tally-skips-helper (list 'skip 'again) 1)
  => (tally-skips-helper (list 'again) 2)
  => (tally-skips-helper (list) 2)
  => 2
  

• We need tally to start as 0, so we write the primary procedure as

  (define tally-skips
    (lambda (lst)
      (tally-skips-helper lst 0)))
  

• What should you do if you want to watch one of these in action on a different input? You can insert some calls to display in the body of the procedure. For example,
• In Scheme ...

  (define tally-skips-helper
    (lambda (lst tally)
      (display (list 'tally-skips-helper lst tally))
      (newline)
      (cond
        ((null? lst) tally)
        ((eq? (car lst) 'skip)
         (tally-skips-helper (cdr lst) (+ 1 tally)))
        (else (tally-skips-helper (cdr lst) tally)))))
  

• This strategy won't work nearly as well with the first tally-skips.

Lab, Continued

• Continue The lab on list recursion.
• Be prepared to reflect.