CSC151.02, Class 20: Numeric Recursion
Admin:
* Reminder about Thursday evening talk (7pm) "Feminism and Science Ed"
* Exams due tonight!
* Don't cheat. Reflect on what cheating is. Sign the statement after you're sure you haven't cheated.
* Do we need to cite stuff from class? No.
* Number and name your pages in any convenient way (by hand, with your text editing program, with a rubber stamp ...)
* How do we show partial work? Usually, you write some Scheme code and include your comments and what you were thinking as Scheme comments.
Overview:
* Really quick discussion of numeric recursion
* Lab
Basic ideas of recursion, revisited yet again
* Take a big problem, breaking it down into a smaller problem, solving the smaller problem, and relating that solution to the solution of the bigger problem.
* Defining a procedure in terms of itself.
* The call to "itself" must involve a "smaller" argument.
* It's easy to make lists smaller: take the cdr.
* What else can we make smaller and eventually reach a stopping point?
* Natural numbers (non-negative integers)
* To make smaller: subtract 1
* Stop when: you've reached 1 or 0.
E.g., factorial
0! = 1
n! = n * (n-1)! for all n > 0
(define factorial
(lambda (n)
(if (= n 0)
1
(* n (factorial (- n 1))))))
Start the lab. Be prepared to give me the general form of a recursive procedure over the natural numbers.
Reflections:
* Some people prefer (zero? n) to (= n 0)
* Some people prefer (<= n 0) to (= n 0)
* Why is iota so painful to write?
* You stop with n-1 rather than n
* You need to put the stuff at the end rather than the beginning
/Approximate ways to write iota/
* Using snoc
(define iota-0
(lambda (n)
(if (zero? n)
null
(snoc (- n 1) (iota (- n 1))))))
* In terms of another procedure
(define iota-1
(lambda (n)
(if (= n 0)
null
(reverse (count-down (- n 1))))))
* By using a helper that keeps track of the current value
(define iota-2
(lambda (n)
(iota-2-helper (0 n))))
(define iota-2-helper
(lambda (current n)
(if (= current n)
null
(cons current (iota-2-helper (+ current 1) n)))))
* By using a helper that keeps track of the values accumulated so far
(define iota-3
(lambda (n)
(iota-2-helper null n)))
(define iota-3-helper
(lambda (partial-list n)
(if (zero? n)
partial-list
(iota-3-helper (cons (- n 1) partial-list) (- n 1)))))