sicpsgjd/1/2/jord/notes.org

• 1.2 Procedures and the Processes they Generate
  • 1.2.1 Linear Recursion & Iteration
  • 1.2.2 Tree Recursion
  • 1.2.3 Orders of Growth
  • 1.2.4 Exponentiation
  • 1.2.5 Greatest Common Divisors

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:

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

720

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)

720

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.

1.2.2 Tree Recursion

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

13

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

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:

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

387420489

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)

1.7748299712158738e+26

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)

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

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

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