Book 1.2-1.2.4: Procedures and the Processes the Generate

"The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer."

A procedure is a local pattern describing how something is done, locally.

In order to make these general we need to able to control how the global state of a program influences the local interpretation of a procedure.

This section will cover the prototypical shapes of a program and the time and space complexity associated with the patterns.

I like the idea that programs have 3 fundamental components:

1. Time
2. Space
3. Shape

Example factorial

Linear Recursion Vs. Linear Iterative

; linear recursive

(define (factorial_rec n)
  (if (= n 1)
      1
      (* n (factorial_rec (- n 1)))))

(factorial_rec 6)

; linear iterative

(define (factorial_iter n)
  (define (iter acc c)
    (if (> c n)
        acc
        (iter (* acc c) (+ c 1))))
  (iter 1 1))

(factorial_iter 6)

Comparing Linear Recursion & Linear Iterative

Similarities:

• They both take n steps to compute $n!$
• The domain and range for each procedure is the same

It's in the title, they both grow linearly n

Differences:

• Linear recursive procedures expand and contract characterized by deferring operations.
• Linear iteration doesn't expand / contract is keeps track of the operations with state variables.
• Each point in the iterative process can be described by the state variables.
• Each point in the recursive process needs more information which tracks where in the chain of expansion or contraction it is.

A recursive procedure is one which calls itself and linear recursion is a description of how the procedure evolves. An iterative procedure can be recursive because it calls itself, but it it not linearly recursive because it can be tracked through state i.e. doesn't expand and contract.

In other languages such as C, implementing a recursive procedure always consumes an amount of memory which grows with the number of procedure calls. Unlike Scheme where an iterative recursive call will only take the memory of the number of state variables required for the process to work, this is constant space. The other languages have to resort to using looping constructs.

The author considers the above a defect.

Exercise 1.9

;(define (+ a b)
;  (if (= a 0) b (inc (+ (dec a) b))))

; this process is recursive, it expands and contracts based on deferred operations

; (inc (+ 3 5))
; (inc (inc (+ 2 5)))
; (inc (inc (inc (+ 1 5))))
; (inc (inc (inc (inc (+ 0 5)))))
; (inc (inc (inc (inc 5))))
; (inc (inc (inc 6)))
; (inc (inc 7))
; (inc 8)
; 9

;(define (+ a b)
;  (if (= a 0) b (+ (dec a) (inc b))))

; this process is iterative

; (+ 4 5)
; (+ 3 6)
; (+ 2 7)
; (+ 1 8)
; (+ 0 9)
; 9

Exercise 1.10

Basically write out a bunch of linearly recursive calls until you can't think straight. Then do some more.

;(define (+ a b)
;  (if (= a 0) b (inc (+ (dec a) b))))

; this process is recursive, it expands and contracts based on deferred operations

; (inc (+ 3 5))
; (inc (inc (+ 2 5)))
; (inc (inc (inc (+ 1 5))))
; (inc (inc (inc (inc (+ 0 5)))))
; (inc (inc (inc (inc 5))))
; (inc (inc (inc 6)))
; (inc (inc 7))
; (inc 8)
; 9

;(define (+ a b)
;  (if (= a 0) b (+ (dec a) (inc b))))

; this process is iterative

; (+ 4 5)
; (+ 3 6)
; (+ 2 7)
; (+ 1 8)
; (+ 0 9)
; 9

; Exercise 1.10

; Ackermann's function

;(define (A x y)
;  (cond ((= y 0) 0)
;        ((= x 0) (* 2 y))
;        ((= y 1) 2)
;        (else (A (- x 1) (A x (- y 1))))))

;(a 1 10)
;(a 0 (a 1 9))
;(a 0 (a 0 (a 1 8)))
;(a 0 (a 0 (a 0 (a 1 7))))
;(a 0 (a 0 (a 0 (a 0 (a 1 6)))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 1 5))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 4)))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 3))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 2)))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 1))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 2)))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 4))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 8)))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 16))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 32)))))
;(a 0 (a 0 (a 0 (a 0 64))))
;(a 0 (a 0 (a 0 128)))
;(a 0 (a 0 256))
;(a 0 512)
;1024

;(a 2 4)
;(a 1 (a 2 3))
;(a 1 (a 1 (a 2 2)))
;(a 1 (a 1 (a 1 (a 2 1))))
;(a 1 (a 1 (a 1 2)))
;(a 1 (a 1 (a 0 (a 1 1))))
;(a 1 (a 1 (a 0 2)))
;(a 1 (a 1 4))
;(a 1 (a 0 (a 1 3)))
;(a 1 (a 0 (a 0 (a 0 2))))
;(a 1 (a 0 (a 0 4)))
;(a 1 (a 0 8))
;(a 1 16)
;(a 0 (a 1 15))
;(a 0 (a 0 (a 1 14)))
;(a 0 (a 0 (a 0 (a 1 13))))
;(a 0 (a 0 (a 0 (a 0 (a 1 12)))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 1 11))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 10)))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 9))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 8)))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 7))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 6)))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 5))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 4)))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 3))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 2)))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 1))))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 2)))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 4))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 8)))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 16))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 32)))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 64))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 128)))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 256))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 512)))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 1024))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 2048)))))
;(a 0 (a 0 (a 0 (a 0 4096))))
;(a 0 (a 0 (a 0 8192)))
;(a 0 (a 0 16384))
;(a 0 32768)
;65536
                                                               

;(a 3 3)
;(a 2 (a 3 2))
;(a 2 (a 2 (a 3 1)))
;(a 2 (a 2 2))
;(a 2 (a 1 (a 2 1)))
;(a 2 (a 1 2))
;(a 2 (a 0 (a 1 1)))
;(a 2 4)
;(a 1 (a 2 3))
;(a 1 (a 1 (a 2 2)))
;(a 1 (a 1 (a 1 (a 2 1))))
;(a 1 (a 1 (a 1 2)))
;(a 1 (a 1 (a 0 (a 1 1))))
;(a 1 (a 1 (a 0 2)))
;(a 1 (a 1 4))
;(a 1 (a 0 (a 1 3)))
;(a 1 (a 0 (a 0 (a 1 2))))
;(a 1 (a 0 (a 0 (a 0 (a 1 1)))))
;(a 1 (a 0 (a 0 (a 0 2))))
;(a 1 (a 0 (a 0 4)))
;(a 1 (a 0 8))
;(a 1 16)
;(a 0 (a 1 16))
;(a 0 (a 0 (a 1 15)))
;(a 0 (a 0 (a 0 (a 1 14))))
;(a 0 (a 0 (a 0 (a 0 (a 1 13)))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 1 12))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 11)))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 10))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 9)))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 8))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 7)))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 6))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 5)))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 4))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 3)))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 2))))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 1 1)))))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 2))))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 4))))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 8)))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 16))))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 32)))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 64))))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 128)))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 256))))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 512)))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 (a 0 1024))))))
;(a 0 (a 0 (a 0 (a 0 (a 0 (a 0 2048)))))
;(a 0 (a 0 (a 0 (a 0 (a 0 4096))))
;(a 0 (a 0 (a 0 (a 0 8192)))
;(a 0 (a 0 (a 0 16384))
;(a 0 (a 0 32768)
;(a 0 65536)
;131072

Tree Recursion

; Fibonacci sequence

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

We can compute the fibonacci sequence by using tree recursion (though we shouldn't).

Each computation of n when n is greater than 1 will produce a computation calls itself twice. The definition of n > 1 is $fib(n-1) + fib(n-2)$. Each call to the procedure where n > 1 is creating a branch of two recursive calls. Each of these, depending on the size of n may break out into more branches, soon we have the shape of a tree.

The problem with this method is that there is a lot of redundant computation. That is to say that there is a lot of repeated computations. In the evaluation of $fib(5)$ you end up computing $fib(3)$ 2 times, which within it has more repeated computations for the smaller values of n.

The number of steps required to calculate the fibonacci sequence with this method grows exponentially with the value of n.

Interestingly the space required to calculate fib in this manner does not grow exponentially, instead linearly and in proportion to the depth of the tree this is because we need to keep track of only the nodes above us in the tree.

Linear Recursion

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

Tree Recursion Vs. Linear Iteration

Although linear iteration is far more efficient, the code implementation of the tree recursive fib solution is far closer to the mathematical definition and therefore easier to understand in that respect.

Example: Counting Change

Can a procedure be written to calculate the number of ways we can give change for any given amount of money?

Yes.

; Example: Counting Change

(define (count-change amount) (cc amount 5))
(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount (- kinds-of-coins 1))
                 (cc (- amount (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(count-change 10)

(cc 10 5)
(cc 10 4) 
(cc 10 3) 
(cc 10 2) (cc 0 3) 1
(cc 10 1) (cc 5 2)
          (cc 5 1) (cc 0 2) 1

This procedure will work out the max number of times you can divide an amount by a division of currency until that division is too big and you need to work out how to divide up the remaining amount in the same way. It will always test every division of currency without from the starting amount. Therefore you can see to total number of ways if you don't have to use all of the divisions. It will only return the number of ways you can divide up an amount.

Exercise 1.11

(define (f-rec n)
  (if (< n 3)
      n
      (+ (f-rec (- n 1))
         (* (f-rec (- n 2)) 2)
         (* (f-rec (- n 3)) 3))))

(f-rec 3)
(f-rec 4)
(f-rec 5)

(define (f-iter n)
  (define (iter a b c count)
    (if (= count 0)
        a
        (iter b c (+ c (* 2 b) (* 3 a)) (- count 1))))
  (iter 0 1 2 n))

(f-iter 3)
(f-iter 4)
(f-iter 5)

The iterative process was too hard for me to find without help.

Exercise 1.12

; Exercise 1.12

(define (pascals i j)
  (if (or (= i j) (= j 0))
      1
      (+ (pascals (- i 1) j)
         (pascals (- i 1) (- j 1)))))

(pascals 2 1)
(pascals 4 2)

Exercise 1.13

Righto, so... proof.

$$fib(n) = fib(n-1) + fib(n-2)$$

$$fib(n) = \frac{ϕ^n − ψ^n}{\sqrt{5}}$$

So we can replace the parts.

$$\frac{ϕ^n − ψ^n}{\sqrt{5}} = \frac{ϕ^{(n-1)} − ψ^{(n-1)}}{\sqrt{5}} + \frac{ϕ^{(n-2)} − ψ^{(n-2)}}{\sqrt{5}}$$

$$\frac{ϕ^n − ψ^n}{\sqrt{5}} = \frac{(ϕ^{(n-1)} + ψ^{(n-2)}) - (ϕ^{(n-2)} + ψ^{(n-1)})}{\sqrt{5}}$$

$$\frac{ϕ^n − ψ^n}{\sqrt{5}} = \frac{ϕ^{n}(ϕ^{-1} + ϕ^{-2}) - ψ^{n}(ψ^{-1} + ψ^{-2})}{\sqrt{5}}$$

$$\frac{ϕ^n − ψ^n}{\sqrt{5}} = \frac{ϕ^{n}ϕ^{-1}(1 + ϕ^{-1}) - ψ^{n}ψ^{-1}(1 + ψ^{-1})}{\sqrt{5}}$$

Not sure I believe this step.

$$\frac{ϕ^n − ψ^n}{\sqrt{5}} = \frac{ϕ^{n}ϕ^{-1}(ϕ) - ψ^{n}ψ^{-1}(ψ)}{\sqrt{5}}$$

$$\frac{ϕ^n − ψ^n}{\sqrt{5}} = \frac{ϕ^{n} - ψ^{n}}{\sqrt{5}}$$

Bingo.

Orders of Growth

The amount of computing power required to solve a problem differs from implementation to implementation. Each process requires a different amount of computational resources.

A convenient way to describe the resources required is to have a way to express how much resource is required as the inputs grows larger.

$R(n)$ is the size of the problem. The size of the problem can be measures in any number of ways. $R(n)$ can also measure the amount of storage that is required.

$$Θ(f (n)), written R(n) = Θ(f (n))$$

$$k1 f (n) ≤ R(n) ≤ k2 f (n)$$

This means that for the independent variables k1 and k2. the result of R(n) is between k1 or k2f(n).

A linear recursive process will produce an order of growth $Θ(n)$.

Orders of growth are an indicator of the performance of an algorithm, they are crude.

A linear implementation that required an overhead of size 1000 $1000n$ and another linear implementation which doesn't require the same overhead, i.e. $n$, will both be $Θ(n)$.

Exercise 1.14

(cc 11 5)
(cc 11 4) (cc -39 5)
(cc 11 3) (cc -14 4)
(cc 11 2) (cc 1 3)
(cc 11 1) (cc 6 2) (cc 1 2) (cc -9 3)
(cc 11 0) (cc 10 1) (cc 6 1) (cc 1 2) (cc 1 1) (cc -4 2)
(cc 10 0) (cc 9 1) (cc 6 0) (cc 5 1) (cc 1 1) (cc -4 2) (cc 1 0) (cc 0 1)