recitation 4: recursive/iterative processes ---------------------------------------------------- from webster: recur = to come up again for consideration recursion = something that calls itself iterate = repeating, each time getting closer to the desired result ---------------------------------------------------- important concepts from today * identify whether a process generates a recursive or iterative process * discuss the orders of growth in space & time of a process * given a task, decide if you want to use a recursive approach to solve it * given a recursive process, rewrite it as an iterative process (if possible) * explain why we prefer iterative processs ---------------------------------------------------- How to identify recursive & iterative processes: recursive iterative process process "recursive "iterative recursion" recursion" tail recursive by staring at code: yes yes * is there a RECURSIVE CALL? (it may be indirect) yes no * is there something "wrapped" around the recursive call? (deferred operations) no often * is there an variable that stores the INTERMEDIATE RESULT? yes yes * is there a COUNTER variable? no often * are there helper functions (often needed to keep track of these other variables) by putting an example through the substitution model: wide narrow * what is the "shape" of the rewrites? long long by analysis of space and time required (order of growth): not O(1) O(1) * space -- width of the substitution model (character has to be stored somewhere... ) recursive & * time -- length of substitutions iterative version (each simplification/rewrite takes 1 unit of time) will have same order of growth for time note: there may be weird exceptions to some of these... -------------------------------------------------- are these things recursive/iterative? (define foo (lambda (x) (* x 10))) (define (remainder a b) (if (< a b) a (remainder (- a b) b))) (define (quotient a b) (if (< a b) 0 (+ 1 (q (- a b) b)))) (define (quotient a b) (quotient-helper a b 0)) (define (quotient-helper a b answer) (if (< a b) answer (quotient-helper (- a b) b (+ 1 answer)))) (define (quotient a b) (define (quotient-helper a b answer) (if (< a b) answer (quotient-helper (- a b) b (+ 1 answer)))) (quotient-helper a b 0)) ----------------------------------------------- why do we often write recursive/iterative procedures? * many problems are easy to think about as loops why do many programming guides discourage writing recursive programs? * limited stack depth * limited memory! * encourage the use of for loops (iterative!) ---------------------------------------------------- why do we care more about orders of growth than absolute running time? * scalability: sure it works for a small test case, but what about real world inputs? foo-a foo-b foo-c 10 10 u-sec 5 u-sec 1 u-sec 20 13 u-sec 10 u-sec 8 u-sec 30 15 u-sec 15 u-sec 27 u-sec 100 20 u-sec 50 u-sec 1000 u-sec 1000 30 u-sec 500 u-sec 1,000,000 u-sec exact formula: f(n) 10*(log_10 n) 0.5*n 0.01*n^3 asymptotic bounds: R(n) Theta(log n) Theta(n) Theta(n^2) we can find a k1 & k2 such that k1*f(n) <= R(n) <= k2*f(n) ---------------------------------------------------- Common Orders of Growth: O(1): CONSTANT not recursive/iterative [compute quadratic root] O(log n): LOGARYTHMIC new x = x / k [dictionary lookup, binary search] O(n): LINEAR new x = x - k [sum up a list] O(n log n): for each element, do log(n) work [sorting] O(n^2) or O(n^k): POLYNOMIAL for each element, look at every other element [ n x n matrix/image, distance between cities ] O(k^n): EXPONENTIAL branching [ fibonacci, playing chess ] ---------------------------------------------------- (define (fact x) (if (= x 1) 1 (* x (fact (- x 1))))) (define (fact-iter x) (fact-iter-helper x 1)) (define (fact-iter-helper x answer) (if (= x 1) answer (fact-iter-helper (- x 1) (* answer x)))) ---------------------------------------------------- recipe for making recursive procedures iterative * what can we use as our partial answer? (accumulator) * how do we keep track of what's left to do? (counter) * how do we update these variables? * what's the base case? * write out a table of variable values * often we'll need a helper procedure to keep track of the extra variables ---------------------------------------------------- (define (foo x) (if (< x 1) 0 ((if (even? x) * +) x (foo (- x 1))))) (foo 5) (+ 5 (foo 4)) (+ 5 (* 4 (foo 3))) (+ 5 (* 4 (+ 3 (foo 2)))) (+ 5 (* 4 (+ 3 (* 2 (foo 1))))) (+ 5 (* 4 (+ 3 (* 2 (+ 1 (foo 0)))))) (+ 5 (* 4 (+ 3 (* 2 (+ 1 0))))) (+ 5 (* 4 (+ 3 (* 2 1)))) (+ 5 (* 4 (+ 3 2))) (+ 5 (* 4 5)) (+ 5 20) 25 * can you write an iterative version? (define (foo-iter x) (define (foo-iter-helper x answer) (if (< x 1) answer (foo-iter-helper (- x 1) ((if (even? x) * +) x answer)))) (foo-iter-helper x 0)) (foo-iter 5) (foo-iter-helper 5 0) (foo-iter-helper 4 (+ 5 0)) (foo-iter-helper 4 5) (foo-iter-helper 3 (* 4 5)) (foo-iter-helper 3 20) (foo-iter-helper 2 (+ 3 20)) (foo-iter-helper 2 23) (foo-iter-helper 1 (* 2 23)) (foo-iter-helper 1 46) (foo-iter-helper 0 (+ 1 46)) (foo-iter-helper 1 47) 47 * whoops, wrong answer (+ 1 (* 2 (+ 3 (* 4 (+ 5 0))))) * try again, need to count up instead (define (foo-iter x) (define (foo-iter-helper orig-x x answer) (if (> x orig-x) answer (foo-iter-helper orig-x (+ x 1) ((if (even? x) * +) x answer)))) (foo-iter-helper x 1 0)) (foo-iter 5) (foo-iter-helper 5 1 0) (foo-iter-helper 5 2 (+ 1 0)) (foo-iter-helper 5 2 1) (foo-iter-helper 5 3 (* 2 1)) (foo-iter-helper 5 3 2) (foo-iter-helper 5 4 (+ 3 2)) (foo-iter-helper 5 4 5) (foo-iter-helper 5 5 (* 4 5)) (foo-iter-helper 5 5 20) (foo-iter-helper 5 6 (+ 5 20)) (foo-iter-helper 5 6 25) 25 ---------------------------------------------------- (define mystery (lambda (a b) (mystery-meat 0 a b))) (define mystery-meat (lambda (c a b) (if (> a b) c (mystery-meat (+ c a) (+ a 1) b)))) * write an equivalent procedure that generates a recursive process: (define clarity (lambda (a b) ) ----------------------------------------------------