EBoard 17: First recursion lab

Approximate overview

• Admin
• Lab

Administrative stuff

Reminders on getting help

• Evening tutors are (generally) helpful. Please use them.
• Reach out to me with questions, to set up meetings, whatever.
• Don’t forget about mentor sessions.
• Individual tutors are available if the primary resources do not provide enough help.

Introductory notes

• Please update your csc151 library. See email for details.
  • Sam will attempt to demo.
• Sam was AFK from Friday night to Sunday night. Sorry!
• Grinnell’s Women and Gender Minorities in Computing group is gathering names for those who are interested. If so, please add your name to the sheet going around the room. Meetings are Fridays at 4pm.
• I suck on getting late homework uploaded. Feel free to remind me again. (I may also change how I set up the late dates.)
• Today’s lab is mostly read and interpret, rather than write. We’ll start writing recursive procedures on Wednesday. (At least that’s the plan.)
• It sounds like illnesses are going around campus. Stay masked, get rest, get flu shot, etc.
• It’s okay to nag Sam.

Upcoming activities

Events

• Learning from Alumni, 2pm, Tuesday, Science 3821. Maddie Kirwin ‘17.
• Mentor Session Tuesday at 8pm
• Mentor Session Wednesday at 7pm
• WGMC Friday at 4pm.
• Arcadia this weekend!
  • Arcadia is a play by Tom Stoppard

Other good things

Upcoming work

• No new readings for Wednesday!
• Lab Writeup due Wednesday.
• Mini-Project 4 due Thursday.

Q&A

Silence.

Lab

Prep

• Person nearest the board is A.
• Person furthest from the board is B.
• If you are confused about distance, ask a mentor.

A sample trace (taken from the lab)

    (func-1 9 '(1 8 2))
--> (if (null? '(1 8 2))
        (list 9)
        (cons (car '(1 8 2)) (func-1 9 (cdr '(1 8 2)))))
--> (if #f
        (list 9)
        (cons (car '(1 8 2)) (func-1 9 (cdr '(1 8 2)))))
--> (cons (car '(1 8 2)) (func-1 9 (cdr '(1 8 2))))
--> (cons 1 (func-1 9 (cdr '(1 8 2))))
--> (cons 1 (func-1 9 (cdr '(1 8 2))))
--> (cons 1 (func-1 9 '(8 2)))
--> (cons 1 (if (null? '(8 2))
                (list 9)
                (cons (car '(8 2)) (func-1 9 (cdr '(8 2)))))
--> (cons 1 (if #f
                (list 9)
                (cons (car '(8 2)) (func-1 9 (cdr '(8 2)))))
--> (cons 1 (cons (car '(8 2)) (func-1 9 (cdr '(8 2))))
--> (cons 1 (cons 8 (func-1 9 (cdr '(8 2))))
--> (cons 1 (cons 8 (func-1 9 '(2))))
--> (cons 1 (cons 8 (if (null? '(2))
                        (list 9)
                        (cons (car '(2)) (func-1 9 (cdr '(2)))))
--> (cons 1 (cons 8 (if #f
                        (list 9)
                        (cons (car '(2)) (func-1 9 (cdr '(2)))))
--> (cons 1 (cons 8 (cons (car '(2)) (func-1 9 (cdr '(2))))))
--> (cons 1 (cons 8 (cons 2 (func-1 9 (cdr '(2))))))
--> (cons 1 (cons 8 (cons 2 (func-1 9 '()))))
--> (cons 1 (cons 8 (cons 2 (if (null? '())
                                (list 9)
                                (cons (car '()) (func-1 9 (cdr '()))))))
--> (cons 1 (cons 8 (cons 2 (if #t
                                (list 9)
                                (cons (car '()) (func-1 9 (cdr '()))))))
--> (cons 1 (cons 8 (cons 2 (list 9))))
--> (cons 1 (cons 8 '(2 9)))
--> (cons 1 '(8 2 9))
--> '(1 8 2 9)

Describing the procedure

What does the procedure do?

It puts a value (x) at the end of a list (l)

What does it do in the base case?

When you add x to the end of the empty list, you get the list '(x)

What does it do in the recursive case?

Removes the first element from l (with (cdr l)), adds x to the remainder (with the recursive call), and then puts the first element back at the front (with (cons (car l) ...)).

Does that achieve the goal?

It seems to.

Why?

In general, we recurse through to the end of the list, building up stuff to cons on the front. Then we do all of the delayed cons calls, to reconstruct the rest of the list.

Notes during lab

• func-1 might be called add-to-end.
• func-2 might be called append.
• Note that both take more work than you might think; to add to the end of a list requires that you step through all of the elements of a list!

Great quotations

• “This lab makes much more sense than the reading.”