CSC151 2010S, Class 25: Recursion Basics Overview: * The need for recursion. * Your questions. * Lab Admin: * Reading for tomorrow: Recursion with Helper Procedures. * It's clearly time for another pop-tart day in 151. * Are there questions on Assignment 6? * Please try to finish today's lab on your own. Questions on HW6 * What happens with blue (0,0,255) Chroma = 255 (R-G)/255 + 4 = 0 + 4 = 4 * Can you give an example of rgb-stronger? Sure. > (rgb->string (rgb-stronger (rgb-new 127 0 200))) "127/0/232" * How would I test number 4? (define c (rgb-new ...)) (define d (rgb-change-hue c 249)) (= (rgb->hue-angle d) 249) (= (rgb->saturation c) (rgb->saturation d)) (= (rgb->value c) (rgb->value d)) Recursion: Another form of repetition * (repeat N PROCEDURE PARAMETERS-FOR-THE-PROC) * Calls the procedure N times * Returns: (Officially: Nothing; In practice, sometimes the value of the last call.) * Called primarily for side effects, rather than for a return value * (map PROCEDURE LIST) * A list, same length as the original list * Values are computed by applying the procedure to each * (for-each PROCEDURE LIST) * Returns: (Officially: Nothing; In practice, sometimes the value of the last call.) * Called primarily for side effects, rather than for a return value * Right now, we only have two choices of what to return: * A list of the same length as our parameter (map) * Nothing (repeat, for-each) * Want other things: * Tally: Return a number * Filter: Return a part of the list * We need a way to repeat and compute other values. * Enter recursion Questions * How does the computer know what to do? * It just follows the instructions (define filter-out-non-pop-tart-eaters (lambda (students) (if (null? students) null (if (pop-tart-eater? (car students)) (cons (car students) (filter-out-non-pop-tart-eaters (cdr students))) (filter-out-non-pop-tart-eaters (cdr students)))))) > (fonpte (list "s1" "s2" "s3" "s4" "s5")) -> (if (null? (list "s1" "s2" "s3" "s4" "s5")) ...) -> (if (pop-tart-eater "s1") ...) -> (fonpte (list "s2" "s3" "s4" "s5")) -> (if (null? (list "s2" "s3" "s4" "s5")) ...) -> (if (pop-tart-eater? "s2") ...) -> (cons "s2" (fonpte (list "s3" "s4" "s5"))) -> (cons "s2" (if (null? (list "s3" "s4" "s5")) ...) -> (cons "s2" (if (pte? "s3") ...)) -> (cons "s2" (cons "s3" (fonpte (list "s4" "s5")) -> ... -> (cons "s2" (cons "s3" (fonpte null))) -> (cons "s2" (cons "s3" (if (null? null) null ...))) -> (cons "s2" (cons "s3" null)) -> (cons "s2" (list "s3")) -> (list "s2" "s3")