As said before, an algorithm is essentially an abstract computer program.  As we said as well, often there are many different algorithms for achieving the same task, and we want to find some way to formally compare the different algorithms.  This in turn means that we need to find some way to specify algorithms.

Since our algorithms take an input and produce an output, they are very similar to functions in the mathematical sense (and discuss in some detail below).  After all, functions take an input and produce an output that is specific to that input.  That is, functions always produce the same output on the same intput.  Moreover, since we want out algorithms to be executable by a computer, one could say that an algorithm is a computable function.

Mathematicians started to try to characterize what makes a function computable well before actual computers had been built.  Thus, the earliest definition of computable functions was provided by Alan Turing in 1936 when he defined what he called a "Logical Computing Machine" and what later became known as a Turing machine (http://en.wikipedia.org/wiki/Turing_machine).  Other definitions included lambda calculus, register machines and μ-recursive functions (see http://en.wikipedia.org/wiki/Computable_function for an overview and links to the various definitions that have been proposed). 

The good thing about all these definitions is that they are equivalent.  For example, all functions that are computable if you use Turing machines are also computable if you use lamba calculus, and vice versa, and the same applies for all other definitions.  The bad thing is that it is very hard if not impossible to specify algorithms that do some real work in any of these formalisms, and we therefore need a more intuitive way of specifying algorithms, and fortunately there is.

In order to specify an algorithm, we need the following constructs:

As it turns out, there are two ways in which we can achieve the latter.  We can either use iteration (e.g., for loops) or recursion.  In this course, we will look at iteration.  These constructs are enough to specify algorithms.

To illustrate the following is a very simple example of an algorithm to calculate the sum for the first n numbers, where n is the input:

res = 0;
for(i = 0; i < n + 1; i = i +1) {
   res = res + i;
}
return res;