A selection is a way of choosing between two of more sequences, based
on a condition. In C, selection is achieved using:
if (cond) seq1 else seq2or the switch construct.
Iteration is the repetition of a sequence. In C, this is achieved using while and for loops.
Surprisingly, these three forms are sufficient for constructing any algorithm. If it is possible to construct an algorithm to describe a particular process then such an algorithm can be constructed from sequence, selection and iteration alone.
Example:
Find the factorial of a number.
n factorial (n!) is defined as the product of all the positive integers
up to and including n, 0! is defined as 1. The factorial of a negative
number is undefined.
n! := n*(n-1)*(n-2).....*3*2*1Where := means "is defined as". This can be evaluated by the following algorithm (expressed in C).
0! := 1, n! := n(n-1)!, n>0or
fact(0) := 1, fact(n) := n * fact(n-1), n>0This is called a recursive definition because it is defined in terms of itself. A recursive definition consists of two parts - the end or terminating case (also called the anchor or base) and the recursive or general case. The end case usually gives a value for a specific argument; this allows the recursion to terminate eventually. For example:
fact(3) := 3*fact(2) := 3*2*fact(1) 3*2*fact(1) := 3*2*1*fact(0) := 3*2*1 := 6Here, the definition of fact(0) is used to terminate the recursion.
A non-mathematical example of a recursive definition is that of ancestor.
However, the iterative version will execute faster and use up less storage space.
The reason for this is that, for each recursive call, the arguments and local variables must be saved (by pushing them onto a stack). So, for example, the call factorial(10) will generate 10 recursive calls to factorial. When a call is completed, the arguments and local variables from the calling function must be popped from the top of the stack. All this pushing and popping takes time and occupies storage.
Often it is necessary to choose between a simple, compact and natural recursive algorithm and an iterative one which runs faster and uses less space but is less readable and more difficult to develop.
Using recursion is also appropriate when the data structure to be manipulated is defined recursively. An example of such a structure,is a binary tree. To search a binary tree we used a recursive function.
This is an example of a problem that is very difficult to solve by iteration. Call the pins A,B and C where A is the start pin and C is the end pin.
Suppose there is just one disk. This can be moved directly from A to C. Next suppose there are three disks on A. Suppose we can transfer the top two disks from A to B using C. We can then move the third disk from A to C. It remains only to transfer the two disks from B to C using A.
We have thus reduced the problem to transferring two disks from one
pin to another. This in turn can be reduced to moving one disk from one
pin to another, which we know how to do. The recursive solution for n disks
is
void transfer(int n, char start, char end, char work) { if (n > 0) { transfer(n-1, start, work, end); printf("Move disk from %c to %c\n",start, end); transfer(n-1, work, end, start); } }When called as:
transfer(3,'A','B','C');The function prints:
Move disk from A to B Move disk from A to C Move disk from B to C Move disk from A to B Move disk from C to A Move disk from C to B Move disk from A to B