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

```