Linear Recursion and Iteration#

Linear recursive process:

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

(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 process:

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

Exercise 1.9#

(define (inc x) (+ x 1)) 
(define (dec x) (- x 1)) 

(define (r+ a b) 
  (if (= a 0) b (inc (r+ (dec a) b)))) 
  
(define (i+ a b) 
  (if (= a 0) b (i+ (dec a) (inc b))))

r+ generates a recursive process:

(r+ 4 5) 
=> (inc (r+ 3 5)) 
=> (inc (inc (r+ 2 5))) ; expanding 
=> (inc (inc (inc (r+ 1 5)))) 
=> (inc (inc (inc (inc (r+ 0 5))))) ; 4 deferred operations
=> (inc (inc (inc (inc 5)))) 
=> (inc (inc (inc 6))) ; contracting 
=> (inc (inc 7)) 
=> (inc 8) 
=> 9

i+ generates an iterative process:

(i+ 4 5) 
=> (i+ 3 6) 
=> (i+ 2 7) 
=> (i+ 1 8) 
=> (i+ 0 9) 
=> 9

Exercise 1.10#

(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) => 1024 
(A 2 4) => 65536 
(A 3 3) => 65536 


(define (f n) (A 0 n)) 
(define (g n) (A 1 n)) 
(define (h n) (A 2 n)) 
(define (k n) (* 5 n n))

(f n) computes $2n$, since (A 0 n) => (* 2 n).

(g n) computes $2^n$ since (A 1 n) => (A 0 (A 1 (- n 1))) => (f (g (- n 1))).

(h n) computes $^n{2}$: (A 2 n) => (A 1 (A 2 (- n 1))) => (g (h (- n 1))).

(k n) computes $5n^2$, as stated in the exercise.

Tree Recursion#

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

(fib 6) => 8

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

(fib 6) => 8

Example: Counting Change#

(define (count-change amount)
  (define (cc a n)
    (cond ((< a 0) 0)
          ((= a 0) 1)
          ((= n 0) 0)
          (else (+ (cc a (- n 1))
                   (cc (- a (first-denomination n)) n)))))
  (cc amount 5))

(define (first-denomination kinds-of-coins)
  (vector-ref '#(1 5 10 25 50) (- kinds-of-coins 1)))

(count-change 100) => 292

Exercise 1.11#

Recursive process:

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

(f 5) => 25

Iterative process:

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

(f 5) => 25

Exercise 1.12#

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

(pascal 3 0) => 1 
(pascal 3 1) => 3 
(pascal 3 2) => 3 
(pascal 3 3) => 1

Exercise 1.13#

The constants $φ$ and $ψ$ are the solutions to the golden ration equation $x + 1 = x^2$:

[ \phi = \frac{1+\sqrt{5}}{2}, \ \ \ \ \phi = \frac{1-\sqrt{5}}{2}. ]

The Fibonacci sequence is defined recursively by

[ \begin{aligned} \operatorname{Fib}(0) &= 0,\newline \operatorname{Fib}(1) &= 1,\newline \operatorname{Fib}(n) &= \operatorname{Fib}(n-1) + \operatorname{Fib}(n-2). \end{aligned} ]

Lemma. $\operatorname{Fib}(n)$ is equal to $f(n) = \frac{φ^n - ψ^n}{\sqrt{5}}$.

Proof. First, we will demonstrate three base cases. When $n = 0$,

[ f(0) = \frac{φ^0 - ψ^0}{\sqrt{5}} = \frac{1-1}{\sqrt{5}} = 0 ]

When $n = 1$,

[ f(1)=\frac{φ^1 - ψ^1}{\sqrt{5}} = \frac{\frac{1+\sqrt{5}}{2} - \frac{1-\sqrt{5}}{2}}{\sqrt{5}} = \frac{\frac{2\sqrt{5}}{2}}{\sqrt{5}} = 1 ]

When $n = 2$,

[ \begin{aligned} f(2) &= \frac{φ^2 - ψ^2}{\sqrt{5}} \newline &= \frac{(\frac{1+\sqrt{5}}{2})^2 - (\frac{1-\sqrt{5}}{2})^2}{\sqrt{5}} \newline &= \frac{\frac{(1+\sqrt{5})^2 - (1 - \sqrt{5})^2}{4}}{\sqrt{5}} \newline &= \frac{((1+\sqrt{5}) - (1 - \sqrt{5})) \ ((1+\sqrt{5}) + (1-\sqrt{5}))}{4 \sqrt{5}} \newline &= \frac{(2\sqrt{5})(2)}{4\sqrt{5}} \newline &= 1. \end{aligned} ]

Now comes the inductive step:

[ \begin{aligned} f(n-1) + f(n-2) &= \frac{φ^{n-1} - ψ^{n-1}}{\sqrt{5}} + \frac{φ^{n-2} - ψ^{n-2}}{\sqrt{5}} \newline &= \frac{(φ^{n-1} + φ^{n-2}) - (ψ^{n-1} + ψ^{n-2})}{\sqrt{5}} \newline &= \frac{φ^n \ (φ^{-1} + φ^{-2}) - ψ^n \ (ψ^{-1} + ψ^{-2})}{\sqrt{5}} \newline &= \frac{φ^nφ^{-1} \ (1 + φ^{-1}) - ψ^nψ^{-1} \ (1 + ψ^{-1})}{\sqrt{5}} \newline &= \frac{φ^nφ^{-1} \ (φ) - ψ^nψ^{-1} \ (ψ)}{\sqrt{5}} \newline &= \frac{φ^n - ψ^n}{\sqrt{5}} \newline &= f(n). \end{aligned} ]

By induction, $f(n) = \operatorname{Fib}(n)$ for all $n$. $\blacksquare$

Theorem. $\operatorname{Fib}(n)$ is the closest integer to $\frac{φ^n}{\sqrt{5}}$, where $φ = \frac{1 + \sqrt{5}}{2}$.

Proof. It suffices to show that the absolute difference is less than one half:

[ \begin{aligned} \left\lvert \operatorname{Fib}(n) - \frac{φ^n}{\sqrt{5}} \right\rvert &< \frac{1}{2} \newline \left\lvert \frac{φ^n - ψ^n}{\sqrt{5}}-\frac{φ^n}{\sqrt{5}}\right\rvert &< \frac{1}{2} \newline \left\lvert -\frac{ψ^n}{\sqrt{5}}\right\rvert &< \frac{1}{2} \newline \frac{|-ψ^n|}{\sqrt{5}} &< \frac{1}{2} \newline |ψ|^n &< \frac{\sqrt{5}}{2}. \end{aligned} ]

Since $|ψ| < 0.619 < 1$, we have $|ψ|^n < 1 < \frac{\sqrt{5}}{2}$ for all $n$. $\blacksquare$

Orders of Growth#

Exercise 1.14#

Imports: Example: Counting Change count-change

(count-change 11) => 4

Here is the process generated by #!scheme (count-change 11):

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

Orders of growth:

Steps: $\Theta(n^5)$ because there are 5 types of coins.
Space: $\Theta(n)$ because the maximum depth of the tree grows linearly.

Remember: for a tree-recursive process, space is proportional to the maximum depth of the tree, and the number of steps is the number of leaves.

Exercise 1.15#

(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine theta)
  (if (<= (abs theta) 0.1)
      theta
      (p (sine (/ theta 3.0)))))

a. The procedurepis evaluated five times for (sine 12.15):

(sine 12.15)
~> (p (sine 4.05))
~> (p (p (sine 1.35)))
~> (p (p (p (sine 0.45))))
~> (p (p (p (p (sine 0.15)))))
~> (p (p (p (p (p (sine 0.05)))))) ; five times until theta <= 0.1

b. During the process, p is evaluated $k$ times such that $\theta / 3^k < 0.1$. Solving for $k$ gives $k = \log10\theta / \log3$, thus the number of steps for sine grows as $\Theta(\log n)$. The interpreter must maintain the stack for that number of calls to p, so the space complexity is also $\Theta(\log n)$.

Exponentiation#

Imports: Compound Procedures square

Recursive, naive: $\Theta(n)$ time, $\Theta(n)$ space.

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

(expt 2 5) => 32

Iterative, naive: $\Theta(n)$ time, $\Theta(1)$ space.

(define (expt b n)
  (define (iter counter prod)
    (if (= counter 0)
        prod
        (iter (- counter 1) (* prod b))))
  (iter n 1))

(expt 2 5) => 32

Recursive, succesive squaring: $\Theta(\log n)$ time, $\Theta(\log n)$ space.

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

(fast-expt 2 5) => 32

Exercise 1.16#

Imports: Compound Procedures square

Iterative, successive squaring: $\Theta (\log n)$ time, $\Theta(\log n)$ space.

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

(fast-expt 2 5) => 32
(fast-expt 2 100) => 1267650600228229401496703205376

Exercise 1.17#

Recursive, naive: $\Theta(n)$ time, $\Theta(n)$ space.

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

(* 5 4) => 20

These are taken as primitives:

(define (double x) (+ x x))
(define (halve x) (/ x 2))

Recursive, sucessive doubling: $\Theta(\log n)$ time, $\Theta(\log n)$ space.

(define (fast-* a b)
  (cond ((= b 0) 0)
        ((even? b) (double (fast-* a (halve b))))
        (else (+ a (fast-* a (- b 1))))))

(fast-* 5 4) => 20

Exercise 1.18#

Imports: Compound Procedures double halve

Iterative, successive doubling: $\Theta(\log n)$ time, $\Theta(1)$ space.

(define (fast-* a b)
  (define (iter c a b)
    (cond ((= b 0) c)
          ((even? b) (iter c (double a) (halve b)))
          (else (iter (+ c a) a (- b 1)))))
  (iter 0 a b))

(fast-* 5 4) => 20