C++ Week 16

Recursive Procedures and Functions II

Building a binary search tree

Consider a list of numbers 5, 3, 8, 7, 2, 10, 6

If we put them in a binary search tree in order, we want each number (and its node) to be added to the left tree of a node if it is less than the node's own value, otherwise we add it to the right hand tree of that node. The resulting tree will look like this:

The code to do the insertion of the numbers is as follows:

void insert(Binode*& troot, int x)
{  if (troot == NULL) troot = new Binode(x);
   else if (x < troot->n) insert (troot->left, x);
   else insert (troot->right, x);
}

If you were reading the numbers from a file, say, then you would have a loop to read a number and insert it into the tree with a call such as insert(root, num);

The Towers of Hanoi

This is a famous puzzle. You have three towers on which you can stack a series of discs of different sizes. The task is to move the discs one at a time from the first tower to the third, but:

• You can move only one disc at a time
• At the end of each move you must always replace a disc on top of one of the towers, i.e. no putting them on the floor
• You may not put a larger disc on top of a smaller one.

When you have only one disc, the solution is trivial: move the disc from tower A to tower C.

When you have two discs, you move the small one onto tower B, leaving just one disc on tower A and a space on tower C. Then we can reuse the solution for one disc by moving the bigger disc from A to C, and finally move the small disc from B to C. Believe it or not we have our solution already!

When we come to three discs, we can break down the solution into its constituents. We use the solution for two discs to move all of the discs except one onto tower B so we can move the biggest disc across to from tower A to tower C. Then we use the solution for two discs to move the remaining discs from tower B to tower C.

With four discs we apply the three-disc solution to move the top three onto the spare tower, then we move the bottom one across, then we apply the three-disc solution again to move the three from the spare tower to the final tower.

Each procedure is based on the one before - Move discs onto the 'spare' tower until you have only one disc left, move that across to the destination tower, then move the discs from the spare tower to their final destination. No matter how many discs there are, we will eventually be able to move all the discs across. The solution for n discs is based on the solution for n-1 discs, and the solution for 1 disc is trivial.

Let's look at some code. We need a procedure that will take a start position and end position and the number of discs to be moved:

void hanoi (char start_pos, char end_pos, char spare_pos, int n)
{  if (n > 1)
      hanoi(start_pos, spare_pos, end_pos, n-1);
   cout << "Move disc from " << start_pos << " to " << end_pos << endl;
   if (n > 1)
      hanoi(spare_pos, end_pos, start_pos, n-1);   
}

void hanoi (char start_pos, char end_pos, char spare_pos, int n)
{  if (n > 0)
   {  hanoi(start_pos, spare_pos, end_pos, n-1);
      cout << "Move disc from " << start_pos << " to " << end_pos << endl;
      hanoi(spare_pos, end_pos, start_pos, n-1);
   }
}

Recursion in language

Software that processes language tends to be recursive, because language is recursive. You can start with a sentence such as "She was going skiing." Then you can embed this in another sentence such as "You said that she was going skiing." This longer sentence now contains something which is itself a sentence. And we can do it again - "She told me that you said that she was going skiing." And so on. If we keep doing it, the sentence might become unwieldy and hard to follow, but not ungrammatical. If you had a sentence() procedure that analysed sentences like these, you would expect it to contain a call to sentence().

The same goes for programming languages. Think of the structure of an if statement in C++:

if ( boolean_condition )
    statement ;

Actually, languages exhibit something called indirect recursion. As well as having an if statement which contains an if statement (direct recursion), you can have an if statement which contains a while loop which contains an if statement (recursion at one remove) or an if statement which contains a while loop which contains a for loop which contains a switch which contains an if statement (recursion at several removes).

The part of the compiler that analyses the syntax of a program (it's called the parser) is likely to have a procedure to analyse a statement - let's call it analyse_statement(). It will decide, on the basis of the first word, what kind of statement it is and will then call another procedure to handle that kind of statement - analyse_if_statement() or analyse_while_statement() or whatever. Let's suppose it's dealing with an if statement. analyse_if_statement() will check that the parentheses are there around the boolean expression, perhaps calling yet another procedure to check the boolean expression itself, and will then call analyse_statement(). So procedure A has called procedure B which has called procedure A. The (here indirect) recursion in the parser mirrors the recursion in the language.

Notes on R. Mitton's lectures by S.P. Connolly, edited by R. Mitton, 2000