there are numerous ways to calculate 6!

linear recursive approach:

(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))
(factorial 6)

linear iterative approach:

(define (factorial n)
  (fact-iter 1 1 n))
(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))
(factorial 6)

here are the shapes of the two approaches, using the substitution model:

;; linear recursive
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

;; linear iterative
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

deferred operations

the functions "stacking up" in the
l.r. model above

recursive process

characterized by a chain of deferred
operations

iterative process

state can be summarized by fixed number of
state variables

linear recursive process

a recursion where the chain of deferred
operations grows linearly with n

linear iterative process

an iteration where the number of steps
grows linearly with n

the iterative approach maintains its own state, explicitly.
when using recursion, state is hidden.

!! don't confuse a recursive process with a recursive procedure

tail recursion

a language implementation that executes iterative
processes in constant space, even if described by
a recursive procedure

languages such as c consume memory with each procedure call, even if
the described process is iterative. this is not tail recursive. the
IEEE standard for scheme requires that implementations be tail
recursive.

          -- > 0		  if n = 0
        /
fib(n)  ---- > 1		  if n = 1
        \
          -- > fib(n-1)+fib(n-2)  else

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+
               (fib (- n 1))
               (fib (- n 2))))))
(fib 7)

(define (fib n)
  (fib-iter 1 0 n))
(define (fib-iter a b count)
  (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1))))
(fib 8)

the first impl traverses a tree. useful, but number of steps is very
high, even with small inputs. the second impl is blazing fast by
comparison, as a linear iter.

computational resources

n is a param that measures the size of a problem
R(n) is the amt of resources that n requires
ϴ(f(n)) is R(n)'s order of growth

growth can be constant, linear, exponential etc. "big o" shit

the following algorithms in §1.2 will be logarithmic in growth

how to compute an exponent?
for
b base
n positive integer exponent
bⁿ = b * bⁿ-1
b⁰ = 1

linear recursive process, ϴ(n) steps, ϴ(n) space:

(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))
(expt 9 9)

linear iterative process, ϴ(n) steps, ϴ(1) space:

(define (expt b n)
  (expt-iter b n 1))
(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                 (- counter 1)
                 (* b product))))
(expt 35 17)

fast as hell method:

(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))
(define (even? n)
  (= (remainder n 2) 0))
(fast-expt 5 5)

a gcd is the largest int that can divide 2 ints with no remainder
given ints a, b; r is the remainder of a/b
gcd(a, b)==gcd(b, r) # br!

euclid's algo (book 2 proposition 2):
gcd(206,40) = gcd(40, 6)
= gcd(6, 4)
= gcd(4, 2)
= gcd(2, 0)
= 2

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))
(gcd 81 18)

!! euclid's algo has logorithmic growth

Lamé's theorem

a euclid algo taking k steps to solve a gcd, the
smaller of the two numbers is greater or equal
to the kth fibonacci number