CSC151, Class 17: List Recursion

Overview:
* Patterns of recursion
* Questions on recursion?  
  (Can you articulate them yet?)
* New lab on list recursion
  (Yes, I know you didn't finish the first in class.)
* Reflection
  (Maybe)

Notes:
* Happy "Valentine's day M&M's are much cheaper two days 
  late" day
* Boy, your end-of-week reflections were depressing
* Homework: Lab writeup 2 (Recursion)
* Read: Numeric Recursion
* Grading 151 is near the front of my todo list.
* Why Sam says "Close your eyes"
* What did you think about the Mad Libs assignment?
* View your colleague's Mad Libs online

----------------------------------------

Recursion, revisited:
* Key ideas: 
  Procedures can call *themselves* as helpers
  In order for recursion to work, the argument must become
    "simpler"
  The argument must eventually become simple enough that
    you can answer the question immediately.

Normal form of recursive procedures is

(define proc
  (lambda (val)
    (if (simple-enough-to-compute-immediately? val)
        (compute-immediately val)
        (combine val (proc (simplify val))))))

(define product
  (lambda (lst)
    ; If there's only one number in the list, the product
    ; of that number is that number
    (if (null? (cdr lst))
        (car lst)
        (* (car lst) (product (cdr lst))))))

Question: Some procedures need recursive helpers; some can
  be defined recursively directly.  How do you decide?
Answer: In some cases, you'll note that you have to keep
  track of some thing or things in addition to the parameter
  you're shrinking.  In those cases, you will often need a
  recursive helper.

Question: Can you show me a pattern?
Answer: I'll try

(define proc
  (lambda (val)
    (helper val initial-extra)))

(define helper
  (lambda (val extra-info)
    (if (simple-enough-to-compute-immediately? val)
        (compute-immediately val extra-info)
        (combine val extra-info (helper (simplify val)
                                        (update extra-info))))))
(define product
  (lambda (lst)
    (product-helper val 1)))

(define product-helper
  (lambda (remaining-values product-so-far)
    (if (null? remaining-values)
        product-so-far
        (product-helper (cdr remaining-values)
                        (* product-so-far (car remaining-values))))))

;; Precondition: lst is not empty

(define product
  (lambda (lst)
    (product-helper (cdr lst) (car lst))))

----------------------------------------

REFLECTION:

* Recursion can induce brain freezes.

* Yes, it's much harder than I make it look
  + What should I make the intitial value be?
    It depends on what the purpose of the extra parameter is
  + What should the purpose of the extra parameter be?
    It depends on how you're using it?
  + How should you use it?
    It depends on ...

* Tally-Skips, two strategies

(define tally-skips
  (lambda (lst)
    (cond
      ((null? lst) 0)
      ((equal? (car lst) 'skip) (+ 1 (tally-skips (cdr lst))))
      (else (tally-skips (cdr lst))))))

(define tally-skips
  (lambda (lst)
    (tally-skip-helper