The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity. In becoming an expert photographer, for example, one must learn how to look at a scene and know how dark each region will appear on a print for each possible choice of exposure and development conditions. Only then can one reason backward, planning framing, lighting, exposure, and development to obtain the desired effects. So it is with programming, where we are planning the course of action to be taken by a process and where we control the process by means of a program. To become experts, we must learn to visualize the processes generated by various types of procedures. Only after we have developed such a skill can we learn to reliably construct programs that exhibit the desired behavior. (pg 31)

Linear Recursion and Iteration

Procedures have shapes, both in time and space.

• Space - determined by deferred operations
• Time - determined by the iterations of a process

As space gets larger so does the amount of information to keep track of. Because time is a measure of the number of steps a process must take to produce an answer, insight is given into the time required to compute. Process Types

• Recursive - Characterized by a chain of deffered operations
• Iterative - State summarized by a fixed number of state variables

A recursive process is different from a recursive procedure. A recursive process refers to how the process evolves. A recursive procedure syntactically refers to itself (indirectly or directly). Thusly, a recursive procedure can be an iterative process.

Exercise 1.9

;; first procedure
(+ 4 5)
(inc (+ (dec 4) 5)
(inc (+ 3 4))
(inc (inc (+ (dec 3) 5)))
(inc (inc (+ 2 5)))
(inc (inc (inc (+ (dec 2) 5))))
(inc (inc (inc (+ 1 5))))
(inc (inc (inc (inc (+ (dec 1) 5)))))
(inc (inc (inc (inc 5))))
(inc (inc (inc 6)))
(inc (inc 7))
(inc 8)
9

;; second procedure
(+ 4 5)
(+ (dec 4) (inc 5))
(+ (dec 3) (inc 6))
(+ (dec 2) (inc 7))
(+ (dec 1) (inc 8))
9

The first procedure is recursive. Each call to the + procedure adds a new inc to the callstack. The second procedure is iterative, because the process has a snapshot of it's state at any given step.

Exercise 1.10

(A 1 10)
1024

(A 2 4)
65536

(A 3 3)
65536

The second half of this two part problem:

(f n) 2n
(g n) 2^n
(h n) 2^2^

Procedure f is simple, in Ackermann's function it will always satisfy the condition x = 0 and return y * 2 which in this case is n * 2. Procedure g is fairly straightforward, it makes a stack of 2 * n calls with a size of n+1. Which is another way of saying 2^n. In procedure h the complexity is higher. This will produce a result which n+1 calls of the g procedure. That is to say 2^2^..n where n determines the number of times to raise the exponent again.