*All code available on GitHub. Drawings/diagrams available here.*

Most of the stuff here is pretty light if you are familiar with Lisps and programming. Some of ideas presented did get me to understand terminology in a new light though (for instance, the idea that functions are declarative while procedures are imperative).

When I first started learning computer science, I wondered if every recursive algorithm could be converted to iteration. I didn’t understand the equivalence until later, where my understanding was in terms of the underlying computer architecture Function calls and iterative looping constructs like `for` are both implemented as `jump` instructions in assembly. . 1.1.7 shows an example of this equivalence.

## Exercise 1.5

The functions look like this in Clojure:

```
(defn p [] (p))
(defn test* [x y]
(if (= x 0) 0 y))
(test* 0 (p))
```

Clojure is applicative order: it evaluates all arguments to `test*`

first. This causes infinite recursion in `p`

. In normal order evaluation, `p`

is not evaluated till it is needed (which is never).

## Exercise 1.6

This was initially surprising to me. It took me a while to realize that how `new-if`

is implemented doesn’t really matter. The applicative order evaluation happens when the arguments (`then-clause`

and `else-clause`

) are evaluated before the function body!

```
(defn new-if [predicate then-clause else-clause]
(cond predicate then-clause
:else else-clause))
(new-if (= 2 3) (print "yes") (print "no"))
;; yesno
```

## Exercise 1.7

Here, we implement a square root function using Newton’s method.

```
(defn sqrt-iter [guess x]
(letfn [(good-enough? [guess x]
(< (Math/abs ^float (- (* guess guess) x))
0.001))
(average [x y]
(/ (+ x y) 2))
(improve [guess x]
(average guess (/ x guess)))]
(if (good-enough? guess x) guess
(recur (improve guess x) x))))
```

This function works for smaller numbers. Did you know Clojure can work with fractions?

```
(sqrt-iter 1 4) ;; 21523361/10761680
```

It fails if the numbers are too big or too small.

```
(sqrt-iter 10 92400000000000000) ;; >>: arithmetic exception
(sqrt-iter 1 0.0005);; >> 0.03640532954316447
```

This is the improved version with the method suggested by SICP:

```
(defn sqrt-iter-2 [first-guess x]
(letfn [(sqrt-iter-2* [prev-guess guess]
(if (good-enough? prev-guess guess) guess
(recur guess (improve guess))))
(good-enough? [prev-guess guess]
(< (Math/abs ^float (- guess prev-guess))
0.001))
(average [x y]
(/ (+ x y) 2))
(improve [guess]
(average guess (/ x guess)))]
(sqrt-iter-2* x first-guess)))
(sqrt-iter-2 1 0.0005)
;; >>: gives 0.02236... which is far more accurate!
```

## Exercise 1.9

Pretty straightforward - though note that since Clojure uses the Java calling conventions, it does not automatically do tail call optimization. From the docs:

[Clojure] provides the recur special operator, which does constant-space recursive looping by rebinding and jumping to the nearest enclosing loop or function frame. While not as general as tail-call-optimization, it allows most of the same elegant constructs, and offers the advantage of checking that calls to recur can only happen in a tail position.

I also tried looking at the jvm bytecode for a simple function with and without using Clojure’s `recur`

. Indeed, without the optimization there is an `invokeinterface`

(function call) rather than a `goto`

(loop).

## Exercise 1.10

```
(defn ackermann [x y]
(cond (= y 0) 0
(= x 0) (* 2 y)
(= y 1) 2
:else (recur (dec x)
(ackermann x (dec y)))))
(ackermann 1 10) ;; > 1024
(ackermann 2 4) ;; > 65536
(ackermann 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))
;; Give concise mathematical definitions for the functions computed by the procedures f, g, and h for positive integer values of n.
;; f = 2n
;;
;; g = (A 1 n) = (A 0 (A 1 (dec n))) = 2 (A 1 (dec n))
;; 2^n
;;
;; h = (A 2 n) = (A 1 (A 2 (dec n))) = (A 1 (A 1 ... (A 1 (A 2 0))))
;; = 2^2^... n times
;; this looks different than the definition on wikipedia?
```