SICP Exercise 1.11
A function f is defined by the rule that f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) if n> 3. Write a procedure that computes f by means of a recursive process. Write a procedure that computes f by means of an iterative process.

(defun f (n)
  "Recursive"
  (cond ((< n 3) n)
             (t (+ (f (- n 1))
                     (* 2 (f (- n 2)))
                     (* 3 (f (- n 3)))))))

(defun f2 (n)
  "Iterative"
  (if (< n 3)
      n
      (f2-iter n 2 1 0)))

(defun f2-iter (count &optional fn-1 fn-2 fn-3)
  (if (< count 3)
      fn-1
      (progn (psetf fn-1 (+ fn-1 (* 2 fn-2) (* 3 fn-3))
                            fn-2 fn-1
                            fn-3 fn-2)
         (f2-iter (- count 1) fn-1 fn-2 fn-3))))

SICP Exercise 1.12
Write a procedure that computes elements of Pascal's triangle by means of a recursive process.

(defun gen-row (lst)
  "Given a list of values of the above row in Pascal's triangle, 
generates the values in the current row except for the leading and
trailing 1"
  (when (> (length lst) 1)
    (cons (+ (first lst) (second lst)) (gen-row (cdr lst)))))

(defun pascal (row)
  "Returns the values in the given row number of Pascal;s triangle"
  (if (eq row 1)
      '(1)
      (append '(1) (gen-row (pascal (- row 1))) '(1))))

SICP Exercise 1.16
Design a procedure that evolves an iterative exponentiation process that uses successive squaring and uses a logarithmic number of steps, as does fast-expt. (Hint: Using the observation that (bn/2)2 = (b2)n/2, keep, along with the exponent n and the base b, an additional state variable a, and define the state transformation in such a way that the product a bn is unchanged from state to state. At the beginning of the process a is taken to be 1, and the answer is given by the value of a at the end of the process. In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.)

(defun my-expt (b n &optional (result 1))
  (cond ((zerop n) result)
        ((evenp n)  (my-expt (* b b) (/ n 2) result))
        (t (my-expt b (- n 1) (* b result)))))

SICP Exercise 1.17
The exponentiation algorithms in this section are based on performing exponentiation by means of repeated multiplication. In a similar way, one can perform integer multiplication by means of repeated addition. The following multiplication procedure (in which it is assumed that our language can only add, not multiply) is analogous to the expt procedure:
(define (* a b)
(if (= b 0)
0
(+ a (* a (- b 1)))))
This algorithm takes a number of steps that is linear in b. Now suppose we include, together with addition, operations double, which doubles an integer, and halve, which divides an (even) integer by 2. Using these, design a multiplication procedure analogous to fast-expt that uses a logarithmic number of steps.

(defun double (x) (+ x x))
(defun half (x) (/ x 2))

(defun fast-mult (a b)
  (cond ((zerop b) 0)
        ((evenp b) (double (fast-mult a (half b))))
        (t (+ a (fast-mult a (- b 1))))))

SICP Exercise 1.18
Using the results of exercises 1.16 and 1.17, devise a procedure that generates an iterative process for multiplying two integers in terms of adding, doubling, and halving and uses a logarithmic number of steps.

(defun my-mult (a b &optional (result 0))
  (cond ((zerop b) result)
        ((evenp b) (my-mult (double a) (half b)  result))
        (t (my-mult a (- b 1) (+ a result)))))

SICP Exercise 1.22
Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in performing the test.
(define (timed-prime-test n)
(newline)
(display n)
(start-prime-test n (runtime)))
(define (start-prime-test n start-time)
(if (prime? n)
(report-prime (- (runtime) start-time))))
(define (report-prime elapsed-time)
(display " *** ")
(display elapsed-time))
Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of (n), you should expect that testing for primes around 10,000 should take about 10 times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the n prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?

;;; Redefine given functions for common lisp
(defun smallest-divisor (n)
  (find-divisor n 2))

(defun find-divisor (n test-divisor)
  (cond ((> (square test-divisor) n) n)
            ((dividesp test-divisor n) test-divisor)
            (t (find-divisor n (+ test-divisor 1)))))

(defun dividesp (a b) (zerop (mod b a)))

(defun square (x) (* x x))

(defun primep (n) (= n (smallest-divisor n)))

(defun timed-prime-test (n)
  (print n)
  (start-prime-test n (get-internal-run-time)))

(defun start-prime-test (n start-time)
  (if (primep n)
      (report-prime (- (get-internal-run-time) start-time))))

(defun report-prime (elapsed-time)
  (print '***)
  (print elapsed-time))

(defun search-for-primes (start end)
  (loop for i from start to end do (timed-prime-test i)))