CSC151.02 2015S, Class 28: Recursion with Helper Procedures =========================================================== * New partners! _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Basics of helper recursion. * A term: Tail recursion. * Why write tail recursive procedures? * Lab! Preliminaries ------------- ### Admin * Friday the 13th falls on Friday this week. Be careful! * I received email from one of you that said (approximately): "I was barely scraping by in my plan to complete the exam and everything else that I have to do this week, and then ..." * My goal is not to push you to the edge; my goal is to support you in learning and to push what you are able to do. * If you are in the first situation, talk to me. I'd rather see representative work. I'd also rather limit your stress level. * Office hours again this week. Mostly normal (MTWF 10:00 plus assorted others). * ### Upcoming Work * [Exam 2](../assignments/exam.02.html). * Electronic version due 10:30 p.m. Thursday the 12th. * Epilogue due 11:00 p.m. on Thursday the 12th. * Printed version due start of class on Friday the 13th. * Reading for Tuesday: * Review [Recursion with Helper Procedures](../readings/helper-recursion-reading.html) ### Extra Credit Opportunities #### Academic * Town Hall on Town Halls, noon or 7:30 p.m. on March 11. * CS Table Friday - Debrief on Tapia Conference on Diversity in Computing. * Post-break: April 1 Scholars Convocation on Implicit Bias. #### Peer Support (Afternoon Section) * Belly Dancing Club Wednesday, 7-8 p.m. in Bucksbaum Dance Studio #### Miscellaneous (Extra Credit) * Fill out the American College Health Association's National College Health Assessment survey. (Yes, your response can be "I filled out the survey.") Almost all of the class has filled out the survey. Let's reach 100%! TODAY IS THE LAST DAY! ### Other Good Things (No Extra Credit) ### Assorted Exam Notes and Questions _I know I can't ask you a direct question about the exam, but could you answer the following?_ > You *can* ask me a direct question about the exam. I may not answer it, or a I may answer it obliquely. But you are certainly permitted to ask. _Any hints?_ > I've added hints to a few problems in which people asked for hints, particularly the one on speeding up code. You will also find it useful to look more deeply at the Q and A section of the exam, because the questions people ask can provide hints. _Have two people spent at least four hours on the exam or completed the exam?_ > Yes. That's among the reasons that there are now only seven problems. _Q (from Sam): What do you expect to get from the expression `(> x (and y z))`? (I think this is intended to mean "if x is greater than both y and z".) I find it useful to think about concrete values: What is `(> 3 (and 5 1))`?_ > A (from "volunteer"): We evaluate inside out, so we have to evaluate `(and 5 1)`. That's probably false because it's senseless. Worse yet, it might be an error message. Perhaps it's 1. It is 1! `and` evaluates parameters, left to right, and stops at the first false. If there are no false values, it returns the last one (1). ### Questions Review of Normal Recursion -------------------------- Let's look at a recursive procedure you've already written: irgb-tally-dark. Goal: Count how many colors in a list of integer-encoded RGB colors are "dark". How do we start writing a recursive procedure? (define irgb-tally-dark (lambda (colors) (if (_test_) _the_result_of_the_base_case_ (_do_something_ (irgb-tally-dark (cdr colors)))))) Let's start filing things in (define irgb-tally-dark (lambda (colors) (if (null? colors) 0 (_do_something_ (irgb-tally-dark (cdr colors)))))) Now, if we can tally the rest (thanks magic recursion fairy), we just need to look at the car (define irgb-tally-dark (lambda (colors) (if (null? colors) 0 (if (irgb-dark? (car colors)) (+ 1 (irgb-tally-dark (cdr colors))) (irgb-tally-dark (cdr colors)))))) Sarah will be upset if you nest `if` statements. (define irgb-tally-dark (lambda (colors) (cond [(null? colors) 0] [(irgb-dark? (car colors)) (+ 1 (irgb-tally-dark (cdr colors)))] [else (irgb-tally-dark (cdr colors))]))) Let's evaluate (irgb-tally-dark (list black white black black)) ; Is the list null? No ; Is the car dark? Yes. (+ 1 (irgb-tally-dark (cdr (list black white black black)))) ; Do the cdr! (+ 1 (irgb-tally-dark (list white black black))) ; Is the list null? No ; Is the car dark? No (+ 1 (irgb-tally-dark (cdr (list white black black)))) ; Do the cdr! (+ 1 (irgb-tally-dark (list black black))) ; Is it null? No. ; Is the car dark? Yes. (+ 1 (+ 1 (irgb-tally-dark (cdr (list black black))))) ; Do the cdr (+ 1 (+ 1 (irgb-tally-dark (list black)))) ; Is it null? No ; Is the car dark? Yes/ (+ 1 (+ 1 (+ 1 (irgb-tally-dark (cdr (list black)))))) ; cdr! (+ 1 (+ 1 (+ 1 (irgb-tally-dark null)))) ; Is null null? Yes! (+ 1 (+ 1 (+ 1 0))) (+ 1 (+ 1 1)) (+ 1 2) 3 Can we get Scheme to act more like a human being and count as it goes? Remaining Count --------- ----- (black white black black) 0 (white black black) 1 (black black) 1 (black) 2 () 3 We want to write a procedure to keep track of two things, the list of remaining colors and the count of dark colors we've seen so far (define irgb-tally-dark-colonel (lambda (remaining tally) (cond [(null? remaining) tally] [(irgb-dark? (car remaining)) (irgb-tally-dark-colonel (cdr remaining) (+ 1 tally))] [else (irgb-tally-dark-colonel (cdr remaining) tally)]))) (define irgb-tally-odds-colonel (lambda (remaining tally) (display (list 'irgb-tally-odds-colonel remaining tally)) (newline) (cond [(null? remaining) tally] [(odd? (car remaining)) (irgb-tally-odds-colonel (cdr remaining) (+ 1 tally))] [else (irgb-tally-odds-colonel (cdr remaining) tally)]))) This model is nice because: * You can design procedures by making tables * You can get Scheme to tell you what's happening Basics of helper recursion -------------------------- A term: Tail recursion ---------------------- Why write tail recursive procedures? ------------------------------------