EBoard 18: Writing recursive procedures
Approximate overview
Administrative stuff
Introductory notes
- If Sam doesn’t respond to notes, feel free to bug him.
- You should see only one part to the lab today. If you don’t, please
reload. And if the lab code has two problem 2’s, please reload that,
too.
- I don’t remember the exact details, but the Dean said that they
surveyed students and 2/3 of you are feeling fairly stressed
right now.
- Yes, that’s more than normal.
- Yes, it’s great if you are not feeling stressed.
- But if you are stressed, you are not alone.
- We will work on trying to keep the stress managable in 151.
(Insert evil laugh.)
- Missing class generally increases stress, rather than decreasing it.
Upcoming activities
Events
- Mentor Session Wednesday at 7pm
- Convocation Thursday at 11am: John Garrison and Dustin Dixon, two
of Grinnell’s best faculty!
- Don’t tell them I said that.
- CS Extras Thursday at 4pm: CLS stuff, Science 3821
- WGMC Friday at 4pm.
- Arcadia this weekend!
- Arcadia is a play by Tom Stoppard
- Tickets are “on sale” at noon today.
- 7pm Monday the 11th: Jillian Peterson on The Violence Project.
Other good things
Upcoming work
Notes from prior lab
- As we hope you noticed from the traces, one important aspect of
the kind of list recursion we’re doing is that it “builds up” a
bunch of delayed procedure calls. For example, near the end
of the trace of
add-to-end (func-1), we see something like
(cons 1 (cons 8 (cons 2 (func-1 9 '())))), with lots of
delayed calls to cons.
- That building up of delayed calls is, in effect, how
this kind of recursion works.
- Tracing really helps us understand recursion.
- We’ll also learn other kinds of recursion.
func-2 was how we might write append. Note that append
incurs some “costs”, since we have to step through the list until
we hit the end.
- We hope that you remember this cost when you are tempted to
use
append.
- You’ll discover something similar about
length.
- Notes reminder: When you discover something in lab, like “Oh, this
stupidly-named procecedure adds to the end of a list”, it’s probably
worth taking notes so that when you have a LA that asks you to
add to the end of a list, you have the code right there in your
notes (or in your brain).
Q&A
Can we use the code from earlier MPs on MP4?
Yes, provided you cite yourself.
Where is the line for the tickets for the play.
Bucksbaum box office.
Lab
Prep
- Person nearest the board is A.
- Person furthest from the board is B.
- If you are confused about distance, ask a mentor.
- Please read through the initial procedures!
Notes during lab
Why do we ask you to identify the parts of recursive procedures?
To give you a better sense of the design of recursive procedures.
To help you start to identify patterns in the design of recursive
procedures. For example, you may have noticed that we have used
two base-case tests for recursive procedures over lists: “Is the
list empty?”, with (null? lst) and “Does the list have only
one element”, with (null? (cdr lst)).
To give us a common vocabulary to talk about recursive procedures.
To give you practice reading code.
Notes on MP4
;;; (count-word word words) -> integer?
;;; word : string?
;;; words : listof string?
;;; Count how many times word appears in words (ignoring case)
(define count-word
(lambda (word words)
(tally (section string-ci=? <> word) words)))