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