August 1999
AP207 : ADVANCED PROGRAMMING TECHNIQUES

QUESTION 3

Total Marks: 20 Marks

 Click here to access other questions

SUGGESTED SOLUTIONS
Solutions and allocated marks are indicated in green.
Return to Question 3
(a) (i) Describe what is meant by a recursive procedure.

(ii) Explain what is meant by the base case of a recursive function.

 [2]

[2]
(i)
  • A recursive procedure is one which calls itself
  • until a condition is reached.

(ii)

  • The base case is the condition which causes the procedure to stop calling itself
  • and climb back up the recursive stack.

 
(b) In mathematics, N! (known as N factorial ) can be computed using the formula N! = N * ( (N-1) ! )
The base case, 0!, is defined as being 1. Write a recursive Pascal function, called Factorial, which takes an integer N, and returns N!.		 [4]
A sample definition of Factorial follows:

FUNCTION Factorial (N : Integer) : INTEGER
BEGIN
       IF N=0 THEN
           FACTORIAL := 1
       ELSE
           FACTORIAL := N*FACTORIAL (N-1);
END;

 
(c) Give the expression AB - C * D - E / F / ( G - H ),

(i) Rewrite this expression in fully bracketed form.

(ii) Convert the expression into post fix form.

  

[2]

[2]

(i) The expression should read: (((Apic4.gif (80 bytes)) - (C * D) + (E/F) / (G - H)))

(ii) Post fix form A, B,pic5.gif (161 bytes)C, D, *, - , E, F, /, G, H, -, /, +

 
(d) Binary tress can be used to model arithmetic expressions. To model a simple arithmetic expression, a node in the tree contains an integer, and an operation. An operation is a variable of the following type :
TYPE OpType = (Int, Add, Subtract);

The leaves of the tree contains just integers; each integer is represented by a node which contains an int in the operation field, and an int in the value field, and no left or right sub-trees. In contrast, the branches of the tree contain operations, which are one of the binary operations given above, and left and right sub-expression trees.

Give a definition of such a binary tree.

  

 

 

 

 

[4]
A sample definition of a binary tree follows:

TYPE Tree   = ^TreeNode;
       Tree     =     RECORD
                                op         :  OpType;
                                data      :  Integer;
                                Left       :  Tree;
                                Right     :  Tree;
                          END;

 
(e) Write a recursive function that determines the height of a dynamic binary tree, such as the one described above. [4]
A sample of definition of a function Height Tree follows:

FUNCTION HeightTree(root : Tree) : Integer;
VAR left, right. Integer;
BEGIN
      IF(root == Nil) THEN
           HeightTree:= 0
      ELSE
      BEGIN
             left:= HeightTree(root. ^Left);
             right:= HeightTree(root. ^Right);
             If(left > right) THEN
                 HeightTree:= 1 + left
             ELSE
                    HeightTree:= 1 + right;
       END;
END;