EBoard 22: Recursion (Section 1)

_Please follow the standard start-of-class routine.

Warning! You are being recorded (and transcribed) (provided the technology is working correctly).

Approximate overview

• Administrivia
• Pop quiz
• Recursion basics
• Examples!
• Converting to Scheme

Administrative stuff

Introductory Notes

• There’s no lab today, so I’m going to announce all the token events today. I will return to the “Sam talks less” experiment.
• I’m also continuing the “pop quiz” experiment.
• Congratulations to our football team for another two victories!
  • We have one more home game, on November 14.
• You will soon be registering for courses for the spring. I hope you’ll consider taking CSC-161.
• I sent out answers to most of the October 16 quizzes over the weekend. Let me know if you didn’t receive them.
• One of you wrote the following on your MP1 redo. “ChatGPT helped revise the code and documentation using the assignment instructions and grader feedback.”
  • You may not use AI-based programming tools in this course!
  • If you did, make an appointment to chat with me.
• “I’m not going to make our 8am class. Can I show up at 9:30 or 2:40?”
  • I’d prefer that you were not awake at 2am. You need sleep!
  • I’d prefer that you made it to the section you are registered for, but I understand needing sleep.
  • It’s better to make it to one section than none.
• Don’t forget to use the cards to figure out where you sit each day.

Upcoming work

• Due Tuesday, 2026-10-27
  • Readings
    • Read Recursion basics
    • Read Recursion magic
    • Submit reading response on Gradescope
  • Mini-project 2 redo
    • Submit redo on Gradescope
    • When submitting a mini-project redo, please include a file called CHANGES.txt that describes what you’ve changed.
    • If you don’t submit the CHANGES.txt file, they won’t grade it.
• Due Thursday, 2026-10-29
  • Readings (forthcoming)
  • Lab writeup (forthcoming)
  • Mini-project 1 second redo
    • Submit redo on Gradescope
    • When submitting a mini-project redo, please include a file called CHANGES.txt that describes what you’ve changed.
• On Friday, 2026-10-30
  • NEW Quiz/LA on list recursion (today, Wednesday, and Friday)
  • Makeup Quiz/LA on testing
  • Makeup Quiz/LA on local bindings
  • Makeup Quiz/LA on collaboration
  • Makeup Quiz/LA on lists and list operations
  • Makeup Quiz/LA on conditionals
  • Makeup Quiz/LA on compose, cut, and section
  • Makeup Quiz/LA on tracing
  • Makeup Quiz/LA on decomposition
  • Makeup Quiz/LA on procedures

Upcoming activities

Scholarly

• Tuesday, 27 October 2026, Noon–1:00 p.m., JRC 224C. CS Table
• Tuesday, 27 October 2026, 6:00–8:00 p.m., JRC 101. Hold the Line: Defending Free, Fair, and Safe Elections
• Thursday, 29 October 2025, 11:00 a.m.–Noon, JRC 101. Scholars’ Convocation: Dan Reynolds on Are We There Yet? The Humanities as a Journey

Artistic/Cultural

• Any day. Visit the GCMOA for at least 30 minutes.
• Thursday, 29 October 2026, Noon–1:00 p.m. Bucksbaum 263 - Fitzgibbons Music Seminar. Total Immolation: Gamelan Towards the Collapse of the Sun.
• Thursday, 29 October 2026, 4:00–5:30 p.m., Wall Theatre. Acting Through Musical Song Workshop with Rachel Kelsey
• Saturday, 31 October 2026, 7:30–10:30 p.m., Harris Cinema. RHPS
• Saturday, 31 October 2026, 8:00–9:00 p.m., Gardner. James Ivy and Band
• Saturday, 31 October 2026, 8:00–9:30 p.m., Herrick. Halloween “Spooktacular” Organ Concert (I’m not sure which organs they are playing; perhaps hearts and lungs.)

Multicultural

• Tuesday, 27 October 2026, 11:30 a.m.–1:00 p.m. The Kernel (HSSC A1231). Filipino Heritage Month Panel
• Friday, 30 October 2026, 4:10–5:00 p.m., HSSC N1170. Middle of Everywhere (Somewhere)

Peer

Musical, theatric, sporting, academic, and similar events involving this section’s students are welcome.

Wellness

• Monday, 26 October 2026, 8:00–9:00 p.m., Prayer Garage in the CRSSJ. Meditation Group
• Tuesday, 27 October 2026, 12:15–12:45 p.m., GCMoA. Yoga in the Museum
• Tuesday, 27 October 2026, 4:30–6:00 p.m., Bear P103. Wellness Yoga
• Tuesday, 27 October 2026, 5:00–8:00 p.m., HSSC North Auditorium. Therapy Dogs
• Wednesday, 28 October 2026, 4:15–5:45 p.m., It’s a secret. Forest Bathing

Misc

• Fill out the College AI survey at https://bit.ly/ACM-AI-Survey. There’s no need to submit evidence; just a reflection.
  • It would be nice if more of you did this!
• Wednesday, 28 October 2026, 4:30–6:30 p.m., Burling. Open Education Trick or Treat
• Wednesday, 28 October 2026, 4:30–6:30 p.m., Harris Concert Hall. Grinnell Gathers: Volunteer Fair
• Wednesday, 28 October 2026, 5:00–7:00 p.m., JRC 209. QuestBridge Slime Event
• Wednesday, 28 October 2026, 8:00–9:00 p.m., Science 3820. Mentor Session
• Thursday, 29 October 2026, 8:00–9:00 p.m., Science 3820. Mentor Session

Other good things

These do not earn tokens, but are worth your consideration.

• Friday, 30 October 2026, 7:00–9:00 p.m. Darby Gym. Volleyball vs. Beloit
• Saturday, 31 October 2026, 11:00 a.m.–1:00 p.m., Springer Field. Men’s Soccer vs. Cornell College
• Saturday, 31 October 2026, 1:00–3:00 p.m. Darby Gym. Volleyball vs. Lake Forest (sorry, no bathing)
• Saturday, 31 October 2026, 1:30–3:30 p.m., Springer Field. Women’s Soccer vs. Cornell College

Pop quiz

• What is decomposition?
• Numbers: What does remainder do?
• Drawings: List three functions to make shapes.
• Strings: How do we convert all the characters in a string to uppercase?
• Drawings: What function puts one drawing vertically over another?

  +-----+
  | One |
  +-----+
+---------+
|   Two   |
+---------+

Recursion basics

• Recursion is one of the core mechanisms for achieving repetition.
• Has some similarity to decomposition.
  • Decomposition: Break a complex problem down into smaller problems and combine the solutions to the smaller problems into the solution to the big problem.
  • Recursion: Solve a complex problem by solving a simpler version of the same problem and then using that solution to solve our more complex.
• At some point, we have a problem so simple that we can solve it directly.

Examples!

Yay! Role playing.

Assumptions:

• The president wants to do as little work as possible.
• However, our contract with the UGSDW suggests that the no person at Grinnell can delegate the same task they received, they must make it “simpler”

Problem one: Count the cards

• Remove one, pass the rest to your assistant
• Ask your assistant to count the rest
• Add 1 to that result

In solving problems this way, we have to think about a few things

• “How do we simplify the problem?” For lists, it’s almost always “Take the cdr”
• When is the problem simple enough that we can solve it without additional help? For lists, “If the list is empty …”; “If the list has one element …”
• What do we do with the solution to the simpler problem. Varies significantly.

Problem two: Sum the cards

• Make the problem simpler: Take one out
• Ask the assistant to sum the dollar amounts
• Add the assistant’s answer to your number, return the result
• Note: When there’s only one card, you can just read the number on the card.
• Note: If you get no cards, you could return zero. [Sam likes this, when possible]

Problem three: Find the largest card

• Make the problem simpler: Take away one card
• Ask your problem to find the largest card in the rest
• This time, we stop with one card left, rather than zero
• In that case the largest card is that one card.
• When you hear the result, you take the larger of your card and the other person’s card.

How would you change this to find the name on the largest card.

• You need to pass back the value and the name.

Scheme thoughts

• How do we find the larger of two cards? max
• How do we decide if there’s only one card?
• How do we pass back two values?

Converting our solutions to Scheme

;;; (count lst) -> integer?
;;;   lst : list?
;;; Counts how many elements are in the list.
(define count
  (lambda (lst)
    (if (null? lst)
        0
        (+ 1 (count (cdr lst)))))) ; remove 1, count the rest, add 1 to the result

;;; (sum lst) -> real?
;;;   lst : (list-of real?)
;;; Add up all the elements in the list.
(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (+ (car lst) (sum (cdr lst))))))
        ; remove an element, sum the rest; add the one we removed

    (sum (list 5 1 2 6))
--> (+ (car (list 5 1 2 6)) (sum (cdr (list 5 1 2 6))))
--> (+ 5 (sum (cdr (list 5 1 2 6))))
--> (+ 5 (sum (list 1 2 6)))
--> (+ 5 (+ (car (list 1 2 6)) (sum (cdr (list 1 2 6)))))
--> (+ 5 (+ 1 (sum (cdr (list 1 2 6)))))
--> (+ 5 (+ 1 (sum (list 2 6))))
--> (+ 5 (+ 1 (+ (car (list 2 6)) (sum (cdr (list 2 6))))))
--> (+ 5 (+ 1 (+ 2 (sum (cdr (list 2 6))))))
--> (+ 5 (+ 1 (+ 2 (sum (list 6)))))
--> (+ 5 (+ 1 (+ 2 (+ (car (list 6)) (sum (cdr (list 6)))))))
--> (+ 5 (+ 1 (+ 2 (+ 6 (sum (cdr (list 6)))))))
--> (+ 5 (+ 1 (+ 2 (+ 6 (sum null)))))
--> (+ 5 (+ 1 (+ 2 (+ 6 0))))
--> (+ 5 (+ 1 8))
--> (+ 5 9)
--> 14