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