CSC151.01 2014F, Class 24: Recursion Basics =========================================== * Continue partners! * Enjoy food-like substances! _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Some challenges. * The idea of recursion. * Challenges, re-expressed in Scheme. * Expressing recursion in Scheme. * Lab. Preliminaries ------------- ### Admin * Office hours * Normal (MThF 1:45-3:15; walking 1:15-1:45) * In the Grill 8:00-9:30 am Fri * In my office 8:00-9:30 am Tue and Thu * Evening review sessions tonight at 8pm and Thursday at 8pm * Daytime review session Thursday at 10:00 a.m. * Quiz 5 will be returned Friday. (We had a mixup with one student who still needs to take it.) ### Upcoming Work * No writeup today! (There will be a writeup on this lab, but it will be assigned Friday.) * [Exam 2](../assignments/exam.02.html) * Reading for Friday: * Reread [Recursion Basics](../readings/recursion-basics-reading.html) * Quiz Friday ### Topics for Friday's Quiz _My quiz policies will continue through this week. You may bring a page of notes. You will not have a time limit, although I will encourage you to try to finish in ten minutes._ * Lists, particularly `cons`, `car`, `cdr`, and `null?` * We might ask you to write instructions to build a list. * We might give you some instructions and ask yo to interpret them. * We might challenge you to think about lists and non-lists (issues raised by the now-renamed `one-two`, `won-too`, and `want-to`) * `image-compute!` * We might ask you to interpret some code. ("Sketch the image that this code creates ...") * We might ask you to write instructions to create a particular image (given verbally or pictorially). * We might do a hybrid ("Fill in the blanks to achieve ...") * Local bindings with `let` and `let*` * The relationship(s) between the two * Ordering of `let` and `lambda` * Any previous topics are also fair game, although they will probably be incorporated in the previous kinds of problems. * We might ask for an anonymous procedure * We might have problems that require conditionals * We might combine the earlier list procedures with the newer ones * ... ### Cool Things Coming to Campus * Two versions of _Anna Christie_! * Live Streaming of Verdi's _Macbeth_, Saturday at 11:55 a.m. * Pop-up Exhibit, Thursday October 9th, all day in BCA 132 ### Extra Credit Opportunities #### Academic * Grinnell Prize events this week (particularly events related to the prize winners whose project involves Web tools) * Artist Talk, Wednesday October 8th at 4:15pm in BCA 152 Rewriting the Application Programming Interface (API) for Art Making * BCC Faculty Chat, Tuesday, October 14, 7pm #### 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 * The College's version of _Anna Christie_, Oct. 9-12 (SB plays Marthy) * Men's Tennis (???) * Women's Tennis (???) #### Miscellaneous * Fill in the Grinnell College Web Survey at ### Questions Some challenges --------------- Context: * We know that the algorithms you write depend on some basic operations. * Basic operations you are allowed: * Anything you've learned earlier in the semester (plus a few other obvious ones) * Determine whether or not a list is empty * If a list is nonempty, you can hand the remainder of the list to someone else, and ask them a question (almost any question) * Count a stack of cards * Ask your neighbor to count all but the first * Add 1 to their result * Count even numbers in a list of numbers * Ask your neighbor to count the number of even numbers in the cdr * If your card is even, add 1 * Otherwise, add 0 * Make a list of even numbers from a list of numbers * Ask your neighbor to make the list of even numbers from the cdr * If your card is even, cons the card on the the result you got from your neighbor * Otherwise, use the result you got from your neighbor The idea of recursion --------------------- * You can solve a problem on a list by * Asking a question about the car of of the list * Asking someone else the same question with the cdr of the list * Combining the results * "Someone else" can use the same instructions * At some point, we reach a problem that we can solve vacuously (e.g., when we have the empty list) Expressing recursion in Scheme - The problems --------------------------------------------- ; Given a list, find out how many values are in the list (define my-length (lambda (lst) (if (null? lst) 0 (+ 1 (my-length (cdr lst)))))) _How does this work?_ (my-length '(1 2 3 4)) => (if (null? '(1 2 3 4)) 0 (+ 1 (my-length (cdr '(1 2 3 4))))) => (if #f 0 (+ 1 (my-length (cdr '(1 2 3 4))))) => (+ 1 (my-length (cdr '(1 2 3 4)))) => (+ 1 (my-length '(2 3 4))) => (+ 1 (if (null? '(2 3 4)) 0 (+ 1 (my-length (cdr '(2 3 4)))))) => (+ 1 (if #f 0 (+ 1 (my-length (cdr '(2 3 4)))))) => (+ 1 (+ 1 (my-length (cdr '(2 3 4))))) => (+ 1 (+ 1 (my-length '(3 4)))) => (+ 1 (+ 1 (if (null? '(3 4)) 0 (+ 1 (my-length (cdr '(3 4))))))) ... => (+ 1 (+ 1 (+ 1 (my-length (cdr '(3 4)))))) => (+ 1 (+ 1 (+ 1 (my-length '(4))))) => (+ 1 (+ 1 (+ 1 (if (null? '(4)) 0 (+ 1 (my-length (cdr '(4)))))))) ... => (+ 1 (+ 1 (+ 1 (+ 1 (my-length (cdr '(4))))))) => (+ 1 (+ 1 (+ 1 (+ 1 (my-length null))))) => (+ 1 (+ 1 (+ 1 (+ 1 (if (null? null) 0 (+ 1 (my-length (cdr null)))))) => (+ 1 (+ 1 (+ 1 (+ 1 (if #t 0 (+ 1 (my-length (cdr null)))))) => (+ 1 (+ 1 (+ 1 (+ 1 0)))) => (+ 1 (+ 1 (+ 1 1))) => (+ 1 (+ 1 2)) => (+ 1 3) => 4 ; Given a list of integers, count even numbers in the list (define count-evens (lambda (lst) (cond [(null? lst) 0] [(even? (car lst)) (+ 1 (count-evens (cdr-list)))] [else (count-evens (cdr-list))]))) ; Given a list of integers, extract the even values and ; give back a list of those values (define list-evens (lambda (lst) (cond [(null? lst) null] [(even? (car lst)) (cons (car lst) (list-evens (cdr-list)))] [else (list-evens (cdr-list))]))) Expressing recursion in Scheme - General Pattern ------------------------------------------------ (define PROC (lambda (lst) (if (null? lst) SOME-VALUE (COMBINE (car lst) (PROC (cdr lst)))))) (define PROC (lambda (lst) (cond [(null lst?) SOME-VALUE] [(TEST (car lst?)) (COMBINE (car lst) (PROC (cdr lst)))] [else ...]))) Lab ---