• Sit whereever you'd like (except for the reserved seat by the door)
• Food! (Please take only one.)

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Basics of helper recursion.
• A term: Tail recursion.
• Lab.

Preliminaries

Admin

• Office hours today and next week
  • Normal (MThF 1:45-3:15; walking 1:15-1:45)
  • Mornings I will be in various places. If you want to find me, email me.
• Quizzes to be returned tomorrow (assuming that the people who missed on Friday make up Quiz 6 before then)

Upcoming Work

• Writeup: Problems 4l and 5b (due Wednesday): http://bit.ly/151-2014F-w26
• Exam 2 due Tuesday.
  • Epilogue due Wednesday night
• Reading for Tuesday:
  • List Recursion, Revisited

Extra Credit Opportunities

• Yes, you can suggest others
• Yes, you can suggest cool things to do on campus

Academic

• BCC Faculty Chat, Tuesday, October 14, 7pm
• CS Table, Friday: Hear about the Grace Hopper Celebration of Women in Computing

Peer Support

• Football (Saturday at 1pm)
• Swimming October 18: Alumni Weekend
• Karan's radio show 11pm Thursday nights on KDIC
• Evan's radio show 5pm Friday nights on KDIC
• Donna's radio show Sunday midnight on KDIC
• Men's Tennis (???)
• Women's Tennis (???)

Questions

Did you change the exam?

I added some Q&A.

I added some notes on problem 7.

But the questions themselves did not change.

Can you explain problem 7?

Yes. I'll go over it.

How do I get under 11 "words" in that evil problem?

Look at the reading on anonymous procedures.

Basics of helper recursion

• Recursion: Define a procedure in terms of itself.
  • Strange, but makes sense (kindof) if you do the evaluation steps one by one.
  • Requires that whenever a procedure calls itself, it does so on a "simpler" problem.
  • "Magic box" - If you assume that someone else can solve the simpler problem, and build a solution, you can use the same procedure.
• A few things to think about when designing recursive procedures
  • When is the problem easy enough that I can solve it directly? (base case test)
  • What is that solution? (base case result)
  • How do I make the problem simpler?
  • How do I use the solution to the simpler problem to solve the less-simple problem?

• In code

  (define FUNCTION
    (lambda (PARAMS)
      (if (EASY? PARAMS)
          SIMPLE-SOLUTION
          (COMBINE PARAMS (FUNCTION (SIMPLIFY PARAMS))))))
  

• Today: A slightly different pattern

  • When we recurse (or recur), we pass along extra information

• Example: Count the number of objects on the table that aren't tied down.

  Objects Running total '(eraser plastic cookies iphone eraser remote) 0 '(plastic cookies iphone eraser remote) 1 '(cookies iphone eraser remote) 2 '(iphone eraser remote) 3 '(eraser remote) 4 '(remote) 5 '() 6 DONE!

• Code

  (define count-things
    (lambda (lst)
      (count-things-helper lst 0)))
  
  
  (define count-things-helper
    (lambda (lst counter)
      (if (null? lst)
          counter
          (count-things-helper (cdr lst) (+ 1 counter)))))
  

Strategy for building these kinds of recursive procedures

• What will I want to keep track of along the way?
• How do I simplify the problem?
• How do I change the thing that I keep track of along the way?
• Work out an exmaple by hand

Choices of problems to try

• Count how many odd numbers are in a list of numbers
• Extract all of the even numbers in a list

• Keep track of

  • List of Numbers I haven't looked at yet

  • List of even numbers I've already seen

    Remaining Extracted '(3 4 5 6 8 11 42) '() '(4 5 6 8 11 42) '() '(5 6 8 11 42) '(4)
    '(6 8 11 42) '(4) '(8 11 42) '(6 4) '(11 42) '(8 6 4) '(42) '(8 6 4) '() '(42 8 6 4)

We've run out of elements, keep extracted list

    (define extract-evens
      (lambda (lst)
        (extract-evens-helper lst null)))

    (define extract-evens-helper
      (lambda (remaining extracted)
        (if (null? remaining)
            extracted
            (exract-evens-helper (cdr remaining)
                                 (if (even? (car remaining))
                                     (cons (car remaining) extracted)
                                     extracted)))))

A term: Tail recursion