recitation 4: recursive & iterative processes, order of growth
-----------------------------------------------------------------------------------------
How to identify recursive & iterative processes: recursive |iterative process
process | (tail recursive)
by staring at code: ---------------------------------
* is there a RECURSIVE CALL? | yes | yes |
(it may be indirect) | | |
---------------------------------
* is there something "wrapped" around | yes | no |
the recursive call? (deferred operations) | | |
---------------------------------
* is there a variable that stores | no | often |
the INTERMEDIATE RESULT? | | |
---------------------------------
* is there a COUNTER variable? | yes | yes |
| | |
---------------------------------
* are there helper functions (often needed | no | often |
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 (order of growth): ---------------------------------
* space -- width of the substitution model | not O(1) | O(1) |
(characters have to be stored somewhere... ) | | |
---------------------------------
* time -- length of substitutions | anything | anything |
(each simplification/rewrite takes 1 unit of time) | | (same as rec) |
---------------------------------
-----------------------------------------------------------------------------------------
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 inputs?
n 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^k)
we can find constants k1 & k2 such that k1*f(n) <= R(n) <= k2*f(n)
-----------------------------------------------------------------------------------------
Common Orders of Growth: give an example for each
O(1): CONSTANT [e.g., compute quadratic root ]
not recursive/iterative
O(log n): LOGARYTHMIC
new x = x / k [e.g., dictionary lookup, binary search ]
O(n): LINEAR
new x = x - k [e.g., sum up a list ]
O(n log n): [e.g., sorting ]
for each element, do log(n) work
O(n^2)/O(n^k): POLYNOMIAL [e.g., n x n matrix/image, distance between cities ]
for each element, look at every other element
O(k^n): EXPONENTIAL [e.g., fibonacci, playing chess ]
branching trace
-----------------------------------------------------------------------------------------
Write a procedure (divisible? n x) which returns #t if n is divisible
by x, that runs in O(n) time and O(1) space.
; assumes n & x are non-negative integers
(define (divisible? n x)
(cond ((= n 0) #t)
((< n x) #f)
(else (divisible? (- n x) x))))
Write a procedure (prime? n) which returns #t if n is prime and #f
otherwise. What's the order of growth in space & time?
; assumes n is an integer > 1
(define (prime? n)
(define (prime-helper n x)
(cond ((= x 1) #t)
((divisible? n x) #f)
(else (prime-helper n (- x 1)))))
(prime-helper n (- n 1)))
-----------------------------------------------------------------------------------------
what's the order of growth in space & time? recursive or iterative? write the other!
(define (bar a b)
(bar-helper 0 a b))
(define (bar-helper c a b)
(if (> a b)
c
(bar-helper (+ c a) (+ a 1) b)))
it's iterative, O(1) space, O(n) space
the recursive version:
(define (bar-rec a b)
(if (< a b) 0
(+ a (bar-rec (+ a 1) b))))
(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
it's recursive, O(n) space, O(n) space
the iterative version:
(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 (find-e n)
(if (= n 0) 1
(+ (/ (fact n)) (find-e (- n 1)))))