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