EBoard 13 (Section 3): Recursion Lab

Approximate overview

• Administrative stuff [~15 min]
• Racket stuff [~0 min]
• Questions [~15 min]
• Lab [~50 min]

Administrivia

Introductory notes

• Reminder: Friday is a “no 151” day. Please spend class time on something that makes your life better (sleep, getting ahead on work, time reading, etc.)
  • Also: Please give yourself a Friday PSA!
• You should have received a grade sheet from me via email yesterday.
  • Let me know if there are ways I can improve the grade sheets.
• I have written to those of you who struggled on SoLA 1 to offer an individual tutor.
  • If you didn’t get email from me, have been attending mentor sessions, and think you’d benefit from an individual tutor, let me know.
• I have split MP3 into MP3 (problems 1 and 2 from the old MP3) and MP4 (everything else from the old MP3).
  • Both are due a week from tomorrow.
  • If you can get the new MP3 in sooner, our graders would appreciate it. (If I had thought more, I would have kept the due date.)
  • I’ll have the Gradescope entry up tonight, if not sooner.
• Survey response rates
  • Section 1: 16/27 (+1 token)
  • Section 2: 14/26 (+1 token)
  • Section 3: 10/27
  • Let’s try for better response rates next time!

Reminders

• Please say your name when you ask or answer a question (even if I’ve just called you by name).
• Evening tutors are available 7–10 p.m. Sunday through Thursday as well as 3–5 p.m. on Sunday.
• Mentor sessions are Wednesday, 8–9 p.m., Sunday 4–5 p.m., Monday 8–9 p.m.

Upcoming work

• No reading for Friday! We have a “compute differently” day.
• Monday readings forthcoming.
  • We continue to explore list recursion on Monday.
• Today’s lab writeup is due Sunday night.
  • But we hope to finish in lab.
• Quiz 5 due Sunday: Regular expressions
• Mini-Project 2 redo due Sunday the 27th at 10:30 p.m. (sooner is better)
• MP3 due Thursday the 3rd at 10:30 p.m.
  • But if you have it done, submit it asap.
• MP4 due Thursday the 3rd at 10:30 p.m.
  • Yes, we’ll talk about it today

Upcoming Token-Generating Activities

• TONIGHT: Mentor Session
• THURSDAY, 11am, JRC 101, “Physics Is More Than Problem-solving: Building Inclusivity and Belonging by Practicing Professionalism”. Prof Marty Baylor of Carleton College.
• ANYTIME: Visit the current exhibit in the Grinnell Art Museum. (At least 15 min.)
• SUNDAY: Mentor Session

Other Upcoming Activities

• SATURDAY: Men’s Tennis at the Field House

Notes on partnering

Thank you to those of you who filled out the survey!

For partnering: There were more ‘ehs than I’d like. (Okay, any ‘ehs is more than I’d like, but we had about 25% ‘ehs.)

You should see their comments. (Note that there are also positive comments.)

• I feel like I know what the benefits are but for me it’s really lowering my confidence.
• Some of the partners that I’ve had have taken a little bit too much initiative, meaning that I don’t get many chances to be the one driving at times even though I would like to.
• I would appreciate if my partners would be more open to discussing the problem and possible solutions, what worked/didn’t work and why. About half of them so far have done this, and the other half hasn’t. I’m very grateful to the people who have.
• Something that I struggle with and I’ve struggled with other people doing is jumping in too soon to correct smaller mistakes, like the lack of a paren or space. That kind of stuff is good to figure out for everyone, just because I or my partner sees it first doesn’t mean we have to point it out right away (esp. if the partner is still typing)
  • Give me a chance to realize my mistakes before correcting me, more than 2 secs preferably.
• People’s confidence in the material varies greatly from person to person. If I seem to have a slower learning curve than you on the material, it might go quicker for you to dominate the lab, but make sure to slow down a little and make sure your partner understands. If you feel less confident, don’t be afraid to question my code to understand it, and have resources such as readings accessible to you while we’re working on the lab.
• Sometimes I’m placed with a partner who assumes I don’t know what I’m doing, or maybe just that they know more? It’s frustrating when a partner explains way more than what I asked… as in, if I ask what’s the order of arguments for make-string? and they explain what make-string is and how i could use it and what an argument is.
• It’s pretty mixed, There’s some people I adore, due to how excited they are to learn the subject ( and more importantly, are excited to experiment), and others I’d rather avoid simply due to their lack of enthusiasm for the subject.
• Some partners have been pretty quiet. Others have not been checking with me to see if I’m on the same wavelength before moving on to the next question.
• If you understand the material better than me and are quicker on the activities then that is fine, but there are some activities that I would like to test and fiddle around with just to understand what is happening instead of rushing to the next question.
• That I generally do think they’re smart and intelligent people who know what they’re doing and I respect they’re input even if I’m not always great at communicating that
• Copying and pasting old code can save a ton of time when you’re writing the same thing over and over.
• I would like them to know that I am worried sometimes about my partner who knows more than me carrying me on the lab because I don’t have a grasp on what I am doing rather than explaining it to me.
• I hope I haven’t offended anyone by accident! Please feel free to interrupt back if I overstep your personal boundaries. I promise, I’m not trying to do it.
• One needs to learn that only the driver should use the keyboard and when he isn’t driver he should not be grabbing it away from me.
  • It’s been good, but i had one time where I had the keyboard taken, didn’t feel great. It was the class after we talked about it as well.
• “It’s okay for the mosquitoes part”

Sample Quiz Questions

Reading Rex Patterns

In your own words, explain what each kinds of strings each of the following regular expressions describes.

(define r1 
 (rex-concat (rex-string "\"") 
             (rex-char-antiset "\"")
             (rex-string "\"")))

(define r2
 (rex-any-of (rex-char-range #\a #\z)
             (rex-char-range #\A #\Z)
             (rex-char-set "'-")))

(define r3
 (rex-repeat r2))

(define r4
 (rex-concat (rex-char-range #\A #\Z)
             (rex-repeat (rex-concat r3 (rex-string " ")))
             (rex-string "love ")
             (rex-repeat (rex-concat r3 (rex-string " ")))
             (rex-char-set ".?!")))

Using Rex Patterns

Write a procedure, (rex-tally rex str), that counts how many times that the pattern given by rex appears in string.

> (rex-tally (rex-string "a") "alphonse says albert and fatima are alphabetical")
10
> (rex-tally (rex-string "al") "alphonse says albert and fatima are alphabetical")
4
> (rex-tally (rex-char-set "aeiou") "alphonse says albert and fatima are alphabetical")
17
> (rex-tally (rex-concat (rex-string "a")
                         (rex-char-antiset "a")
                         (rex-string "a"))
             "alphonse says albert and fatima are alphabetical")
1
> (rex-find-matches (rex-concat (rex-string "a")
                         (rex-char-antiset "a")
                         (rex-string "a"))
             "alphonse says albert and fatima are alphabetical")
'("a a")

Writing Rex Patterns

Write a regular expression that matches the common form of “words” in English. Words start with a lowercase or uppercase letter and then have a sequence of lowercase letters, apostrophes, and dashes.

Racket/Lab Stuff

None today.

Questions

Reading questions

Can you go over tracing of recursive procedures?

It should be the same as tracing of any other procedure. However, we tend to skip a few steps.

But what you’ll often observe is that we build up a lot of delayed computations that only get done when we reach the base case.

And you’ll get some practice in lab.

Why is cdr pronounced “could-er”?

It’s hard to pronounce things with no vowels. I suppose “code-er” would be funnier.

Between the “big three” list functions and recursive list function, which is more efficient/concise? Are there any special cases where we should use one over the other?

There are so many contextual issues that it’s hard to answer your question. It’s nice to think in terms of the “big three” list functions. But as we’ll see, the “big three” are often implemented with recursion. I tend to prefer that you use the big three, except when you’re learning how to write recursive procedures.

Note: You’ll learn how to write the big three in class. One of the outcomes of this class should be that you can write most of the procedures you use (except for some really basic ones, like + or cons).

What’s going on with (awesum (list 5 2))?

(define awesum
  (lambda (lst)
    (if (null? lst)
        0
        (+ (car lst) (awesum lst)))))

    (awesum (list 5 2))
    ; The list is not null
--> (+ 5 (awesum (list 5 2)))
    ; The list is not null
--> (+ 5 (+ 5 (awesum (list 5 2))))
    ; The list is not null
--> (+ 5 (+ 5 (+ 5 (awesum (list 5 2)))))
    ; The list is not null
--> ...

It keeps expanding forever because we never make the input “smaller”.

What does (awesum (list 5 2)) really result in?

It runs forever, so there is no final result.

Can you use car and cdr outside of recursion?

Yup. Anywhere you have a list you can use car and cdr.

Can you use procedures other than car and cdr in recursion?

Yes, as long as they simplify the parameters. take and drop are a nice pair.

Can two procedures each refer to each other?

Yes. We often call that “mutual recursion”.

Other issues

Do I still have to complete a lab if I missed class?

Definitely! How else will you learn the material?

I’m worried that I’m falling behind. What should I do?

Chill. Different people learn at different rates.

Talk to Sam or the mentors, depending on who you are more comfortable with.

Ask for an individual tutor to help you through things.

Could you not cold call me? It makes me too nervous.

Certainly. Chat with me and I’ll put a mark on your card. But you do need to volunteer.

Can I have SamR’s approval to __?

Talk to me.

Can we get better keyboards? These are really flimsy.

That’s out of my control. Sorry.

I don’t like working in pairs. Can I work alone?

Nope. You should develop skills working with others.

Can you change the due date for quizzes to Sunday?

Sure. But I’ll probably make them due before the mentor session.

MP3

How do I stop my procedure from reading the file more than once.

I would suggest writing a separate procedure, (count-words-from-list list-of-words file-contents) and then make count-words call that. count-words will read the file and pass its contents on to count-words-from-list.

When writing the weird cadar and other procedures, can we use any combination of a’s and ds?

Up to about four, yes. If you’re from Boston, it’s harder to understand though.

Lab

Preparation

Please take the time to chat with your partner. You may want to re-review some of the concerns.

During Lab

• Copy, paste, change is a good way to trace.
• Micah says any/c means “anything” not “any character”
  • It’s “c” for “contract”, which is beyond our understanding in this course.
• I’m sorry that one (1) and el (l) look similar.
• Strangely enough, (*) is 1 and (+) is 0.

Wrapup

• Submit whatever you’ve finished at about 2:15 p.m. Make sure that you write "; SAM SAID I COULD STOP HERE" so that the grader does not attempt to look at more.
• We have you learn tracing, in part, so that you can better understand what’s happening in recursion.
• Congratulations, you get the cheesy department sticker.
  (No, I did not design it.)