Overview

• Admin.
• Basics of helper recursion.
• A term: Tail recursion.
• Lab.

Admin

• Pick new partners!
  • You must work with someone new
• Upcoming EC opportunities
  • Football, 1 pm, Saturday
  • Men's soccer, 1:30 pm, Saturday
  • CS Table Friday: Ambient Belonging
  • ...
• Other upcoming stuff
  • Mentor session 7:30 pm Thursday
  • ...

Basics of helper recursion

#lang racket
(require gigls/unsafe)

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

(define sum2
  (lambda (lst)
    (sum2-helper lst 0)))

(define sum2-helper
  (lambda (lst partial-sum)
    (if (null? lst)
        partial-sum
        (sum2-helper (cdr lst) (+ (car lst) partial-sum)))))

A term: Tail recursion

• In the original sum (sum1), we've delayed a lot of the work (sum (list 1 2 3 4)) => (+ 1 (+ 2 (+ 3 (+ 4 (sum1 null)))))
• In the new version, we do the work as we go, and when we reach the end, we have no work left to do (yay!)
• If you can write recursive procedures that don't have delayed work when they reach the base case, they run a bit more efficiently.
• This is called "tail recursion"

Lab

• Consider 42 - -18 - 23 - 4

  • Do we interpret it as (((42 - -18) - 23) - 4)
  • Or as (42 - (-18 - (23 - 4)))
  • First interpretation, in Scheme (- (- (- 42 -18) 23) 4)
  • Second interpreation, in Scheme (- 42 (- -18 (- 23 4)))

• The brightest value (brightest '("0/0/0" "63/63/63" "127/127/127" "191/191/191" "255/255/255"))

• Let's count total calls based on the length of the list

  • calls(1) = 1 ; Just the outermost
  • calls(2) = 1 + 2*1 = 3 ; The call plus the two recursive calls on length 1
  • calls(3) = 1 + 2*3 = 7 ; The call plus the two recursive calls on length 2
  • calls(4) = 1 + 2*7 = 15 ; The call plus the two recursive calls on length 3
  • calls(n) = 1 + 2*calls(n-1)