EBoard 32: Tail recursion (Section 2)

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

Approximate optimistic overview

  • Administrative stuff
  • Tail recursion
  • Q&A
  • Lab

Administrative stuff

Introductory notes

  • Congratulations to Men’s Tennis on 21st consecutive MWC title.
  • We will be forming groups for mini-project 9 on Wednesday. PLEASE COME TO CLASS! (It’s also okay if you decide to work alone.)
  • To help make the semester a bit more manageable, I will permit Es on second redos (except for MP1).
    • If that affects the work you put into the MP2 or MP3 redo, let me know.
  • I’ve extended the MP4, MP5, and MP6 redos another week.
  • Please please please submit mentor and evening tutor evaluations.
  • Reminder: We’ll have prospies on Friday.

Upcoming activities

Scholarly

Artistic

  • Monday, 21 April 2025, 4:00–5:00 p.m., GCMoA. Poetry Reading by Lívia Stein Freitas
  • All week (I think.) Bucksbaum Basement. Art Exhibit: If you woke up and you were a fish, what would you do?

Multicultural

  • Friday, 25 April 2025, 4:00–5:00 p.m., HSSC N1170 (Global Living Room). Middle of Everywhere: Road Trip Around Spain
  • Saturday, 26 April 2025, 1:00–8:30 p.m., Cleveland Beach. Holi

Peer

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

  • Read articles by your fellow CSC-151 students and comment on them online.
  • Saturday, 25 April 2025, Noon, Baseball field. Baseball vs. Ripon
  • Saturday, 25 April 2025, 2:30 p.m., Baseball field. Baseball vs. Ripon
  • Sunday, 26 April 2025, Noon, Baseball field. Baseball vs. Ripon

Wellness

  • Monday, 21 April 2025, 6:30–8:00 p.m. Dance Studio. Brazilian Jiu-Jitsu
  • Tuesday, 22 April 2025, 12:00–12:45 p.m., Dance Studio. HIIT Training.
  • Tuesday, 22 April 2025, 12:15–12:50 p.m., GCMoA. Yoga in the Museum.
  • Tuesday, 22 April 2025, 4:30–6:30 p.m., BRAC P103 (Multipurpose Dance Studio). Wellness Yoga.
  • Wednesday, 23 April 2025, 6:30–8:00 p.m., Dance Studio. Brazilian Jiu-Jitsu
  • Thursday, 24 April 2025, 12:00–12:45 p.m., Dance Studio. HIIT Training.
  • Thursday, 24 April 2025. 4:30–6:30 p.m., Off Campus. Forest Bathing.
    • Sign ups are required.
  • Friday, 25 April 2025, 6:00–8:00 p.m., Aux Gym. Badminton Club (Smash that bird!)
  • Friday, 25 April 2025, 6:30–8:00 p.m. Dance Studio. Brazilian Jiu-Jitsu
  • Friday, 25 April 2025, 9:00 p.m., Noyce Elbow. Nerf at Noyce.
  • Saturday, 26 April 2025, 4:00–6:00 p.m., Aux Gym. Badminton Club (Smash that bird!)
  • Tuesday, 29 April 2025, 5:00–6:00 p.m., HSSC Atrium. Therapy Dogs.
  • Tuesday, 29 April 2025, 7:15–8:15 p.m., HSSC Atrium. Therapy Dogs.

Misc

  • Tuesday, 22 April 2025, 7:00–8:00 p.m., Science 3820. Mentor Session: Quizzes
  • Wednesday, 23 April 2025, Noon–1:00 p.m., HSSC A2231 (Auditorium) Community Forum
    • “Weekly discussion on legal protections and recourse on issues that higher education and Grinnell College face.”
    • Also online.
    • This week: ???
  • Sunday, 27 April 2025, 7:30–8:30 p.m., Science 3819. Mentor Session

Other good things

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

  • Saturday, 25 April 2025, 1pm, Softball field. Softball vs. Cornell_
  • Saturday, 25 April 2025, 3:30 p.m., Softball field. Softball vs. Cornell_

Upcoming work

Brain dumps

  • I would have liked to have seen more brain dumps of things like vector recursion on the SoLA pre-reflections.
  • That could be “here’s a vector recursive procedure I’ve written” (as best you recall)
  • Or “here’s a pattern”
  • Or just something like “the base case is normally …”; “the recursive case is normally …”.
  • Let’s try that now.

Vector recursion

(define vector-increment-odd!
  (lambda (vec)
    (vio/helper! vec 0)))

(define vio/helper!
  (lambda (vec pos)
    (when (< pos (vector-length vec))
      (when (odd? (vector-ref vec pos))
         (vector-set! vec pos (+ 1 (vector-ref vec pos))))
      (voi/helper! vec (+ pos 1)))))

Randomness

  • There’s a procedure, (random n) that produces an unpredictable number between 0 and n.
  • We can use (vector-ref vec (vector-length vec)) to get a random value in a vector.
  • We can make stupid stories using that principle.
  • In the 7/11 example, we got slightly incorrect results by calling a random procedure more than once. (We use let to help.)

Tail Recursion

Would it be possible for you to run through how to do the reading question. I understand that tail recursion requires that all functions and procedures be done before the recursive call, but I’m not sure how to implement that.

General principles

  • A procedure is tail-recursive if you directly return the recursive result (without, say, adding to it or consing to it or whatever).
  • We often achieve this by adding an “accumulator” as a parameter in a helper. The accumulator gathers the result as we go.
  • In case it wasn’t clear, we’ll often need a helper.

factorial

Normal recursion

(define factorial
  (lambda (n)
    (if (zero? n)
        1
        (* n (factorial (- n 1))))))

Tail recursion

(define factorial
  (lambda (n)
    (helper n 1)))

(define helper
  (lambda (n so-far)
    (if (zero? n)
        so-far ; What I've computed along the way
        (helper (- n 1) (* n so-far)))))

A quick trace

(factorial 5) --> (helper 5 1) --> (helper (- 5 1) (* 5 1)) --> (helper 4 5) --> (helper (- 4 1) (* 4 5)) --> (helper 3 20) --> (helper (- 3 1) (* 3 20)) --> (helper 2 60) --> (helper (- 2 1) (* 2 60)) --> (helper 1 120) --> (helper (- 1 1) (* 1 120)) --> (helper 0 120) --> 120 ```

We tend to use tail recursion “whenever possible” because it ends up being faster than non-tail recursion.

In some cases, tail recursion is not possible. Or overly difficult. (It requires a different way of thinking.)

make-list

Normal recursion

; Make a list of `n` copies of `val`.
(define make-list
  (lambda (n val)
    (if (zero? n)
        null
        (cons val (make-list (- n 1) val)))))

Tail recursion

(define helper
  (lambda (n val so-far)
    (if (zero? n)
        so-far
        (helper (- n 1) val (cons val so-far)))))

(define make-list
  (lambda (n val)
    (helper n val null)))

    (make-list 3 "J")
--> (helper 3 "J" '())
--> (helper 2 "J" (cons "J" '()))
--> (helper 2 "J" '("J"))
--> (helper 1 "J" (cons "J" '("J")))
--> (helper 1 "J" '("J" "J"))
--> (helper 0 "J" (cons "J" '("J" "J")))
--> (helper 0 "J" '("J" "J" "J"))
--> '("J" "J" "J")

Four steps

to (partially) convert a regular recursive function to a tail-recursive fucntion.

  • The base case test seems to be the same.
    • In the tail recursive version, we return so-far, rather than null.
  • The base value gets sent in as the original value of so-far.
  • In the recursive call, we “simplify” the parameter in the same way (- n 1).
  • The stuff outside the recursive call in the original gets moved inside the recursive call in the tail-recursive version; in fact, it gets applied to the so-far.

filter

Normal recursion

(define filter
  (lambda (lst pred?)
    (if (null? lst)
        null
        (if (pred? (car lst))
            (cons (car lst)
                  (filter (cdr lst) pred?))
            (filter (cdr lst) pred?)))))

Tail recursion

(define helper
  (lambda (lst pred? so-far)
    (if (null? lst)
        so-far
        (if (pred? (car lst))
            (helper (cdr lst) pred? (cons (car lst) so-far))
            (helper (cdr lst) pred? so-far)))))

(define filter
  (lambda (lst pred?)
    (helper lst pred? null)))

Whoops, this is backwards

    (filter '(1 2 3 4 5 6) even?)
--> (helper '(1 2 3 4 5 6) even? '())
--> (helper '(2 3 4 5 6) even? '())
--> (helper '(3 4 5 6) even? (cons 2 '()))
--> (helper '(3 4 5 6) even? '(2))
--> (helper '(4 5 6) even? '(2))
--> (helper '(5 6) even? (cons 4 '(2)))
--> (helper '(5 6) even? '(4 2))

How do we fix this to generate the list in the right order?

(define helper
  (lambda (lst pred? so-far)
    (if (null? lst)
        so-far
        (if (pred? (car lst))
            (helper (cdr lst) pred? (cons (car lst) so-far))
            (helper (cdr lst) pred? so-far)))))

(define filter
  (lambda (lst pred?)
    (helper (reverse lst) pred? null)))

Questions

Administrative

When will the SoLA be released?

4pm

Readings

I do not quite understand how list recursion can be generalized using tail recursion.

We can often build up the list backwards as we go, and then reverse it in the last step.

Are we expected to memorize the recursion templates provided in the reading? They seem much more specific than the other procedures we have been given templates for, which didn’t necessarily require memorizing and more so logic.

You don’t have to memorize the templates. But they may help to have in your notes.

What’s the difference between letrec and let*?

let* defines things in sequence. letrec builds recursive procedures. You can’t build a recursive procedure with let*.

Lab

Copyright © Eric Autry, Charlie Curtsinger, Sarah Dahlby Albright, Janet Davis, Nicole Eikmeier, Fahmida Hamid, Priscilla Jiménez, Barbara Johnson, Titus Klinge, Peter-Michael Osera, Leah Perlmutter, Samuel A. Rebelsky, John David Stone, Anya Vostinar, Henry Walker, and Jerod Weinman.

Unless specified otherwise elsewhere on this page, this work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this license, visit http://creativecommons.org/licenses/by-nc/3.0/ or send a letter to Creative Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.

This website was built using Jekyll, Twitter Bootstrap, and the Bootswatch Cosmo Theme.