* 1.2 Procedures and the Processes they Generate
"To become experts, we must learn to visualize the processes generated
by various types of procedures"

 - local evolution :: pattern defined by a procedure about how each
      stage of the process is built off each other

We make statements about the global behavior whose local evolution has
been specified by a procedure.

we will examine common process "shapes"

** 1.2.1 Linear Recursion & Iteration

there are numerous ways to calculate 6!

linear recursive approach:

#+BEGIN_SRC scheme

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

#+END_SRC

#+RESULTS:
: 720

linear iterative approach:

#+BEGIN_SRC scheme

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

#+END_SRC

#+RESULTS:
: 720

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

#+BEGIN_SRC 

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

#+END_SRC

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

** 1.2.2 Tree Recursion

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

#+BEGIN_SRC scheme
  (define (fib n)
    (cond ((= n 0) 0)
	  ((= n 1) 1)
	  (else (+
		 (fib (- n 1))
		 (fib (- n 2))))))
  (fib 7)
#+END_SRC

#+RESULTS:
: 13

#+BEGIN_SRC scheme
  (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)
#+END_SRC

#+RESULTS:
: 21

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.

** 1.2.3 Orders of Growth
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

** 1.2.4 Exponentiation
how to compute an exponent?
for 
  b base
  n positive integer exponent
b^n = b * b^n-1
b^0 = 1


linear recursive process, ϴ(n) steps, ϴ(n) space:
#+BEGIN_SRC scheme
  (define (expt b n)
    (if (= n 0)
        1
        (* b (expt b (- n 1)))))
  (expt 9 9)
#+END_SRC

#+RESULTS:
: 387420489

linear iterative process, ϴ(n) steps, ϴ(1) space:
#+BEGIN_SRC scheme
  (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)
#+END_SRC

#+RESULTS:
: 1.7748299712158738e+26

fast as hell method:
#+BEGIN_SRC scheme
  (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)
#+END_SRC

#+RESULTS:

** 1.2.5 Greatest Common Divisors
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
#+BEGIN_SRC scheme
  (define (gcd a b)
    (if (= b 0)
        a
        (gcd b (remainder a b))))
  (gcd 81 18)
#+END_SRC

#+RESULTS:
: 9

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