1.2 Procedures and the Processes They Generate⁠

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. (Section 1.2)

• A procedure is a pattern for the local evolution of a computation process: how one stage is built on the previous stage.
• The global behavior of a computational process is much harder to reason about.
• Processes governed by different types of procedures generate different “shapes.”
• Computational processes consume two important resources: time and space.

# 1.2.1 Linear Recursion and Iteration⁠

• The factorial of $N$ is defined as the product of the integers on the interval $[1,N]\htmlClass{math-punctuation}{\text{.}}$
• The naive recursive implementation creates a curved shape:

(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

• The iterative implementation maintains a running product and multiplies the numbers from 1 to $N\htmlClass{math-punctuation}{\text{.}}$ This creates a shape with a straight edge:

(factorial 4)
(fact-iter 1 1 4)
(fact-iter 1 2 4)
(fact-iter 2 3 4)
(fact-iter 6 4 4)
(fact-iter 24 5 4)
24

• Both compute the same mathematical function, but the computational processes evolve very differently.
• The first one is a linear recursive process. The chain of deferred operations causes an expansion (as operations are added) and a contraction (as operations are performed).
  • The interpreter must keep track of all these operations.
  • It is a linear recursive process because the information it must keep track of (the call stack) grows linearly with $N\htmlClass{math-punctuation}{\text{.}}$
• The second is a linear iterative process. It does not grow and shrink.
  • It is summarized by a fixed number of state variables and a rule to describe how they should update and when the process should terminate.
  • It is a linear iterative process because the number of steps grows linearly with $N\htmlClass{math-punctuation}{\text{.}}$
• In the iterative process, the variables provide a complete description of the state of the process at any point. In the recursive process, there is “hidden” information that makes it impossible to resume the process midway through.
• The longer the chain of deferred operations, the more information must be maintained (in a stack, as we will see).
• A recursive procedure is simply a procedure that refers to itself directly or indirectly.
• A recursive process refers to the evolution of the process described above.
• A recursive procedure can generate an iterative process in Scheme thanks to tail-call optimization. In other languages, special-purpose looping constructs are needed.

# 1.2.2 Tree Recursion⁠

• With tree recursion, the procedure invokes itself more than once, causing the process to evolve in the shape of a tree.
• The naive Fibonacci procedure calls itself twice each time it is invoked, so each branch splits into two at each level.

In general, the number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree. (Section 1.2.2)

• The iterative Fibonacci procedure is vastly more efficient in space and in time.

# Example: Counting change

Let $f(A,N)$ represent the number of ways of changing the amount $A$ using $N$ kinds of coins. If the first kind of coin has denomination $N\htmlClass{math-punctuation}{\text{,}}$ then $f(A,N) = f(A,N-1) + f(A-D,N)\htmlClass{math-punctuation}{\text{.}}$ In words, there are two situations: where you do not use any of the first kind of coin, and when you do. The value of $f(A,N-1)$ assumes we don’t use the first kind at all; the value of $f(A-D,N)$ assumes we use one or more of the first kind.

That rule and a few degenerate cases are sufficient to describe an algorithm for counting the number of ways of changing amounts of money. We can define it with the following piecewise function:

$$f(A,N) = \begin{cases} 1, & \text{if $A = 0$,} \\ 0, & \text{if $A < 0$ or $N = 0$,} \\ f(A,N-1) + f(A-D,N), & \text{if $A > 0$ and $N > 0$.} \end{cases}$$

Like Fibonacci, the easy tree-recursive implementation involves a lot of redundancy. Unlike it, there is no obvious iterative solution (it is possible, just harder). One way to improve the performance of the tree-recursive process is to use memoization.

# 1.2.3 Orders of Growth⁠

• Different processes consume different amounts of computational resources.
• We compare this using order of growth, a gross measure of the resources required by a process as the inputs becomes larger.
• Let $n$ be a parameter that measures the size of a problem—it could be the input itself, the tolerance, the number of rows in the matrix, etc.
• Let $R(n)$ be the amount of resources the process requires for a problem of size $n\htmlClass{math-punctuation}{\text{.}}$ This could be time, space (amount of memory), number of registers used, etc.
• We say that $R(n)$ has order of growth $Θ(f(n))\htmlClass{math-punctuation}{\text{,}}$ or $R(n) = Θ(f(n))\htmlClass{math-punctuation}{\text{,}}$ if there are positive constants $A$ and $B$ independent of $n$ such that $Af(n) ≤ R(n) ≤ Bf(n)$ for any sufficiently large value of $n\htmlClass{math-punctuation}{\text{.}}$
• The value $R(n)$ is sandwiched between $Af(n)$ and $Bf(n)\htmlClass{math-punctuation}{\text{.}}$
• The linear recursive process for computing factorials had $Θ(n)$ time and $Θ(n)$ space (both linear), whereas the linear iterative process had $Θ(1)$ space (constant).
• The order of growth is a crude description of the behavior of a process.
• Its importance is allowing us to see the change in the amount of resources required when you, say, increment $n$ or double $n\htmlClass{math-punctuation}{\text{.}}$

# 1.2.4 Exponentiation⁠

One way to calculate $b$ to the $n\htmlClass{math-punctuation}{\text{th}}$ power is via the following recursive definition:

$$b^0 = 1, \qquad b^n = b * b^{n-1}.$$

A faster method is to use successive squaring:

$$b^n = \begin{cases} \left(b^{n/2}\right)^2, & \text{if $n$ is even,} \\ b * b^{n-1}, & \text{if $n$ is odd.} \end{cases}$$

# 1.2.5 Greatest Common Divisors⁠

• The GCD of integers $a$ and $b$ is the largest integer that divides both $a$ and $b$ with no remainder. For example, $\gcd(16,28) = 4\htmlClass{math-punctuation}{\text{.}}$
• An efficient algorithm uses $\gcd(a,b) = \gcd(b,a\bmod b)\htmlClass{math-punctuation}{\text{.}}$
• For example, we can reduce (gcd 206 40) as follows:

(gcd 206 40)
(gcd 40 6)
(gcd 6 4)
(gcd 4 2)
(gcd 2 0)
2

• This always works: you always get a pair where the second number is zero, and the other number is the GCD of the original pair.
• This is called Euclid’s Algorithm.
• Lamé’s Theorem: If Euclid’s Algorithm requires $k$ steps to compute the GCD of some pair $(a,b)\htmlClass{math-punctuation}{\text{,}}$ then $\min\{a,b\} ≥ \Fib(k)\htmlClass{math-punctuation}{\text{.}}$

# 1.2.6 Example: Testing for Primality⁠

# Searching for divisors

• One way to test for primality is to find the number’s divisors.
• A number is prime if and only if it is its own smallest divisor.

# The Fermat test

The Fermat test is a $Θ(log(n))$ primality test based on Fermat’s Little Theorem:

If $n$ is a prime number and $a$ is any positive integer less than $n\htmlClass{math-punctuation}{\text{,}}$ then $a$ raised to the $n\htmlClass{math-punctuation}{\text{th}}$ power is congruent to $a$ modulo $n\htmlClass{math-punctuation}{\text{.}}$ (Section 1.2.6)

The test works like this:

1. Given a number $n\htmlClass{math-punctuation}{\text{,}}$ pick a random number $a < n$ and calculate $a^n\bmod n\htmlClass{math-punctuation}{\text{.}}$
2. Fail: If the result is not equal to $a\htmlClass{math-punctuation}{\text{,}}$ then $n$ is not prime.
3. Pass: If the result is equal to $a\htmlClass{math-punctuation}{\text{,}}$ then $n$ is likely prime.
4. Repeat. The more times the number passes the test, the more confident we are that $n$ is prime. If there is a single failure, $n$ is certainly not prime.

# Probabilistic methods

• Most familiar algorithms compute an answer that is guaranteed to be correct.
• Not so with the Fermat test. If $n$ passes the Fermat test for one random value of $a\htmlClass{math-punctuation}{\text{,}}$ all we know is that there is a better than 50% chance of $n$ being prime.
• A probabilistic algorithm does not always give a correct result, but you can prove that the chance of error becomes arbitrarily small.
• We can make the probability error in our primality test as small as we like simply by running more Fermat tests—except for Carmichael numbers.