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")