CSC151.01 2015S, Class 24: Recursion Basics =========================================== * New partners! _Overview_ * Preliminaries. * Admin. * Upcoming Work. * Extra Credit. * Questions. * Background. * The idea of recursion. * Some sample recursive procedures. * Expressing recursion in Scheme. * Lab. Preliminaries ------------- ### Admin * Review session tonight at 7:00 p.m. * Office hours today and tomorrow at 10:00 a.m. * * I'm trying to free hours from about 3:15-4:30 tomorrow. They will appear soon. * Reminder: Please clean up after yourself in 3813 and 3815 and beyond. * Today's class has a slightly different format (because of the topic, not because of the visitors) * Welcome to our prospective students and/or parents. ### Upcoming Work * [Homework 6](../assignments/assignment.06.html). * Due Tuesday at 10:30 p.m. * Optional! Replaces lowest homework grade. * If you don't do the homework, promise to get two hours of extra rest. * Exam 2 to be assigned on Tuesday. Due 10:30 p.m. Thursday the 12th. * No lab writeup for today. * Reading for Tuesday: * Review [Recursion Basics](../readings/recursion-basics-reading.html) ### Extra Credit Opportunities #### Academic * Any of the disability activities this week. * David Berliner lecture Thursday at 7:00 p.m. in Harris. * CS Table Friday - Unknown topic. * Town Hall on Town Halls, noon or 7:30 p.m. on March 11. * Post-break: April 1 Scholars Convocation on Implicit Bias. #### Peer Support (Morning Section) * Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m. * Orchestra Saturday at 2 p.m. in Sebring-Lewis: Musicals, Show Tunes, and Soloists. ### Other Good Things * Belly Dancing Club Wednesday, 7-8 p.m. ### Questions _When will we get grades on homework assignments?_ > By Sunday evening. Background ---------- Approximately seven things that we expect to see in algorithms * Subroutines with parameters (named inputs) * Variables: Things that are defined so that the program will be faster or cleaner. (Names for computed values.) * Conditional: Choose between different possibilities * Repetition: Where you repeat stuff * Subroutines: Helper algorithms * Sequencing (including sequencing by nesting). * Some basic built-in operations. What kinds of repetition have we seen? * `map`: Takes a function and at least one list and applies the function to each element (or groups of elements) - returns a list * `image-variant`: Takes as input an RGB transformation and an image and applies the transformation to each pixel - returns an image * "repeat by hand" * `make-list` makes a list of a particular length * `image-compute` returns a computed image by applying a function at each position. How do we do other kinds of repetition? In Scheme, with recursion. The idea of recursion --------------------- * Given a complex problem, break it down into simpler parts. * Recursion: Given a complex problem, solve a simpler version of the problem, and then use that solution to solve the "bigger" problem. * With lists, we can `car` and `cdr` the list * car takes the first element * cdr takes all but the first element Some sample recursive procedures -------------------------------- To count the number of items in a list * If the list is not empty * Count the number of items in the cdr * Add 1 * Otherwise, it's 0 (define length (lambda (lst) (if (not (null?)) (+ 1 (length (cdr lst))) 0))) Heaviest item in the list * If you have only one item, it's the heaviest * Otherwise * Find the heaviest remaining item * Compare to the car * Return the heavier of the two (define heaviest (lambda (lst) (if (= (length lst) 1) (car lst) (heavier (car lst) (heaviest (cdr lst)))))) (define redder (lambda (color1 color2) (if (> (irgb-red color1) (irgb-red color2)) color1 color2))) (define reddest (lambda (lst) (if (= (length lst) 1) (car lst) (redder (car lst) (reddest (cdr lst)))))) All the red items * If you have no items Expressing recursion in Scheme ------------------------------ Lab ---