EBoard 17: Recursion

This class will be recorded! Its use is limited to members of the class. Please do not share with others.

Approximate overview

  • General administrative stuff [~10 min]
  • Q&A (not on recursion) [~10 min]
  • Tracing let expressions [~15 min]
  • Talk about recursion [~15 min]
  • Lab [~30 min]

Administrative stuff

Notes and news

  • As the overview suggests, today still involves talk
    • I’ll be trying to get you to talk, too.
  • Don’t forget to register for CSC 161. Weinman is awesome.
  • If you’re planning to continue in CS, you might also consider MAT-208.
  • I’d like to hear from more of you in class! Volunteer ideas, questions, whatever. Don’t just wait for me to call on you.
  • Yes, I know that you still don’t have MP2 back. But you do know about the big picture issues. Coming soon.
  • Just in case it’s not clear, we pronounce “lst” as “list” and not as “first”.
  • Mentors will be holding review sessions for the SoLA on email forthcoming. (Sunday and Monday)
  • We have a reference page. Let me know if there are procedures that i have not yet documented.

Tutoring reminders

  • Please use our tutors! They like to work.
  • Evening tutoring will be available
    • 8-10 p.m. Sundays through Thursdays
    • 3-5 p.m. Sundays
    • In the “Drop in tutoring” channel on the CS team.
    • Sam will generally not be available during these times.
  • Individual tutors are also available.

Upcoming activities

Attend (or watch recording) and send a one-paragraph reflection.

  • Noon, TODAY, The Future of the Humanities. (+1 token)
  • 3:30, Saturday, Nov. 21st: Maker Space (+1 token)
  • 7:30-9:30 p.m. Saturday, 21 Nov 2020: Art SEPC Collage, Meet, and Greet (+1 token)

Upcoming work

Q&A

We have like more than a week until MP3-redo is due, right?

Yup.

Will we ever do lab?

I hope so.

Tracing let expressions

Policy for tracing let.

(let ([NAME1 EXP1]
      [NAME2 EXP2]
      ...
      [NAMEn EXPn])
  BODY1
  BODY2
  ...
  BODYm)
  • Evaluate all of the expressions in the bindings.
  • Substitute the bound values for the corresponding variables in the body.
  • Evaluate the expressions in the body. (Usually there’s just one.)
  • Return the value of the last body expression.

Note: let is just a more convenient way to write the following.

(define newfunc
  (lambda (NAME1 NAME2 ... NAMEn)
    BODY1
    BODY2
    ...
    BODYm))
(newfunc EXP1 EXP2 ... EXPn)
  • Evaluate all the expressions
  • Substitute the evluated expressiosn for the parameters in the body
  • Evaluate the body

Or maybe for this

((lambda (NAME1 NAME2 ... NAMEn) BODY1 ... BODYm) EXP1 EXP2 ... EXPn)

But few of us do that.

If you’d prefer, you can rewrite the let into the corresponding lambda. (I don’t generally recommend it.)

What’s the point of the BODY expressions?

Racket does have procedures whose purpose is not to return a value, but to change the state of the world (e.g., to print). That’s typically what the extra body expressions are.

Example of tracing let.

(define a 1)
(define b 2)
(define c 3)

(let ([a 10])
  (let ([b (* a a)])
    (let ([c (+ b a)])
      (list a b c))))

Let’s trace

     (let ([a 10])
       (let ([b (* a a)])
         (let ([c (+ b a)])
           (list a b c))))
--> (let ([b (* 10 10)])
      (let ([c (+ b 10)])
        (list 10 b c)))
--> (let ([b 100])
      (let ([c (+ b 10)])
        (list 10 b c)))
--> (let ([c (+ 100 10)])
      (list 10 100 c))
--> (let ([c 110])
      (list 10 100 c))
--> (list 10 100 110)

Another example of tracing let

(define a 1)
(define b 2)
(define c 3)

(let ([a 10]
      [b (* a a)]
      [c (+ b a)])
  (list a b c))

Let’s trace

    (let ([a 10]
          [b (* a a)]
          [c (+ b a)])
      (list a b c))
--> (let ([a 10] ; We've evaluated the ten
          [b (* a a)] 
          [c (+ b a)])
      (list a b c))
--> (let ([a 10] 
          [b (* 1 a)] ; Substitute for the first a
          [c (+ b a)])
      (list a b c))
--> (let ([a 10] 
          [b (* 1 1)] ; Substitute for the next a
          [c (+ b a)])
      (list a b c))
--> (let ([a 10] 
          [b 1] ; Evaluate the (* 1 1)
          [c (+ b a)])
      (list a b c))
--> (let ([a 10] 
          [b 1] 
          [c (+ 2 a)]) ; Throw in 2 for b
      (list a b c))
--> (let ([a 10] 
          [b 1] 
          [c (+ 2 1)]) ; Throw in a 1 for a
      (list a b c))
--> (list 10 1 3) ; Substitute

Why would someone want to do this?

They are evil.

They lack creativity and always use the same variable names.

Sometimes it seems natural.

(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (+ (car lst) (sum (cdr lst))))))

(define sum
  (lambda (lst)
    (if (null? lst)
        0
        (let ([first (car lst)]
              [lst (cdr lst)])
          (+ first (sum lst))))))

Policy for tracing let*.

(let* ([NAME1 EXP1]
       [NAME2 EXP2]
       ...
       [NAMEn EXPn])
  BODY1
  BODY2
  ...
  BODYm)
  • Evaluate the first expression.
  • Substitute the value of the expression for the name in the rest of the let* expression, both the expressions and the body.
  • Do the same for each binding in sequence.

Note that let* is just another way to write a whole bunch of nexted let expressions.

(let ([NAME1 EXP1])
  (let ([NAME2 EXP2])
    ...
      (let ([NAMEn EXPn])
        BODY1
        BODY2
        ...
        BODYm)...))

Example of tracing let*.

(let* ([a 10]
       [b (* a a)]
       [c (+ b a)])
  (list a b c))

Let’s trace

    (let* ([a 10]
           [b (* a a)]
           [c (+ b a)])
      (list a b c))
--> (let* ([a 10]
           [b (* 10 10)]
           [c (+ b 10)])
      (list 10 b c))
--> (let* ([b (* 10 10)]
           [c (+ b 10)])
      (list 10 b c))
--> (let* ([b 100]
           [c (+ b 10)])
      (list 10 b c))
--> (let* ([b 100]
           [c (+ 100 10)])
      (list 10 100 c))
--> (let* ([c (+ 100 10)])
      (list 10 100 c))
--> (let* ([c 110])
      (list 10 100 c))
--> (let* ([c 110])
      (list 10 100 110))
--> (let* ()
      (list 10 100 110))
--> (list 10 100 110)

Discussion of recursion

Self-check one

;;; (sum numbers) -> number?
;;;   numbers : listof number?
;;; Returns the sum of the numbers in the list.
(define sum
  (lambda (numbers)
    (if (null? numbers)
        0
        (+ (car numbers) (sum (cdr numbers))))))

    (+ 5 (+ 8 (sum (list 2))))
--> (+ 5 (+ 8 (if (null? (list 2)) 0 (+ (car (list 2)) (sum (cdr (list 2)))))))
--> (+ 5 (+ 8 (if (null? (list 2)) 0 (+ (car (list 2)) (sum (cdr (list 2)))))))
--> (+ 5 (+ 8 (if #f 0 (+ (car (list 2)) (sum (cdr (list 2)))))))
--> (+ 5 (+ 8 (+ (car (list 2)) (sum (cdr (list 2))))))
--> (+ 5 (+ 8 (+ 2 (sum (cdr (list 2))))))
--> (+ 5 (+ 8 (+ 2 (sum '()))) ; We could have written (sum (list)))
--> (+ 5 (+ 8 (+ 2 (sum '()))) )
--> (+ 5 (+ 8 (+ 2 (sum '()))))
--> (+ 5 (+ 8 (+ 2 (if (null? '()) 0 (+ (car '()) (sum (cdr '())))))))
--> (+ 5 (+ 8 (+ 2 (if #t 0 (+ (car '()) (sum (cdr '())))))))
--> (+ 5 (+ 8 (+ 2 0))) ; took the true part
--> (+ 5 (+ 8 (+ 2 0)))
--> (+ 5 (+ 8 2))
--> (+ 5 10)
--> 15

Why if must be a keyword.

    (sum (list 1))
--> (if (null? (list 1)) 0 (+ (car (list 1)) (sum (cdr (list 1)))
--> (if (null? (list 1)) 0 (+ (car (list 1)) (sum '())))
--> (if (null? (list 1)) 0 (+ (car (list 1)) (if (null? '()) 0 (+ (car '()) (sum (cdr '()))))))
--> (if (null? (list 1)) 0 (+ (car (list 1)) (if (null? '()) 0 (+ (car '()) (sum (cdr '()))))))
; If we take (cdr '()), it crashes.
; In order for recursion to work, `if` must behave differently than
; normal procedures

Lab

You will just access the .rkt files directly today (at least I hope you will).

The lab is broken into two parts: Things you have to turn in and things you don’t.

Make sure to try to do all of the lab before Monday’s class.

Copyright © Charlie Curtsinger, Sarah Dahlby Albright, Janet Davis, Fahmida Hamid, Titus Klinge, Peter-Michael Osera, Samuel A. Rebelsky, and Jerod Weinman. Selected materials are copyright by John David Stone or Henry Walker and are used with permission.

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.