SICP Section 1.2

Here a procedure is defined. In other languages[such as java], procedures are called methods. It’s interesting how a procedure is defined in this text. Here, it is defined as a pattern for the local evolution of a computational process. What this means is that a procedure is like a general rule, in that it describes how something should be done.

So what is a process?

Say I tell you to multiply a huge number, say 1433 times 3294[without a calculator but using pen and paper]. What would you do? Probably you’d write it down and work it out step by step. The whole grand scheme of things would be called a procedure. The individual steps you’d take would be called a process. As you can well see, each stage of the process builds upon the previous stage to come up with a final answer.

Two types of processes were discussed: 1. Recursive process which is characterized by a chain of deferred operations. 2. Iterative process whose state can be summarized by a fixed number state variables.

Do not, however, confuse a recursive process with a recursive procedure. A recursive procedure is a procedure which calls itself while a recursive process describes how the process evolves.

What is tail recursive? Watch this video on tail recursion for more information.

Another form of recursion is the tree recursion. The process it generates resembles a tree in the sense that there are branches and nodes. Tree recursion is wasteful since it is redundant. This was shown using the example of factorial. Being wasteful[because of redundancy] does not however make this process useless as it can be used to operate on hierarchically structured data which are not numbers.

The concept of “orders of growth” was also discussed. Orders of growth give a rough description of how much resources a computational process consumes. It is crude since it only gives a rough estimation. In this text, 𝟅-notation was used. Look at the following functions:

2x^2 + 2x + 3
x^2
3x^2 + 3

In all the above cases, they take 𝟅(n^2) order of growth to be complete.

The rest of this chapter discusses various algorithms and makes some interesting commentaries on them. A common thread in all of this is converting recursive processes into iterative ones. The orders of growth of various implementations of various algorithms(such as gcd, exponentiantion, primality-check) was examined.

Another interesting thing about this chapter is some of the mathematical concepts which have been introduced e.g. modulo congruence in the Fermat Test.

Something worth mentioning are probabilistic algorithms such as the Fermat test. These algorithms are those in which if a test is failed, then the test condition is certain. However, passing the test does not guarantee a correct solution, but a probable correct solution. This last comment does not mean that the algorithm is useless. Probabilistic algorithms such as the Fermat test are quite reliable in practice. Of course they can be fooled at times, but measures can be put to prevent this.