University of Toronto
csc148 -- Introduction to Computer Science, Fall 1995

Assignment 4: Recursion

Note: This assignment will be marked out of 100. The last 5 marks are for the overall quality of your writing. The marking scheme indicated in this handout is tentative.

Introduction

This assignment is intended to give you experience with recursion. The textbook readings on recursion are: Chapter 9, as well as pages 49-51. Below are some additional topics that the assignment touches on; you may want to review the readings on these topics also:

• Use of stacks. (See Chapter 5.)
• Use of trees. (See Sections 10.1 and 10.2.)
• Re-use of software. (See Section 5.2 for the original version of the software you will be re-using.)
• Evaluation of arithmetic expressions. (See Section 5.2 as well as pages 329-331.)
• Use of graphics. (See Section 8.2 and pages 513-4 of Appendix B.)
• Proofs of recursive subprograms.

In the assignment, you will write (or use or modify) a number of subprograms, rather than writing a larger program starting from scratch. Each of these subprograms is rather short and not particularly difficult.

Part 1. Exercises with Recursion (5 points)

Run the program in figure 1. (See page for instructions on getting a copy of this and other programs needed for the assignment.)

  
Figure 1: Program for part 1 of the assignment.

TURN IN: a sequence of hand drawn diagrams showing the contents of the run stack just before and just after each procedure call, along with a diagram showing the corresponding picture the program has drawn. (See Figure 5.10 of the textbook for an example of a run stack.)

Part 2. Arithmetic Expressions (70 points)

In this part of the assignment, you will make use of re-usable software components to create a program that evaluates arithmetic expressions and draws them. Your program will be based on the case study in Section 5.7 of the textbook. See pages 161-167 for an overview of the program, and Figure 5.9 for the structure of the program. You will be given a directory that contains the software from the textbook, and a basic version of the extended software you are to write.

In this part of the assignment, you must change only one file, namely, part2.ti. The other files should not be changed; you are not to write or modify any modules other than this file.

Start by running the program nevalexp.t, to get a general understanding of what the program does.

Note on file suffix naming conventions: file.t is a main OOT program, file.tu is an OOT unit and file.ti is an OOT include file (see page xviii of the text).

Your task is to expand the software in file part2.ti so it contains a set of procedures that:

(2a)

Draws an expression as a tree (as described below).

(2b)

Draws an expression as a set of nested boxes (as described below).

(2c)

Does one step in the evaluation of the expression, by replacing the bottommost, leftmost operator (if any) with the value that it produces; this modifies the tree by replacing an operator node and its two children with a value node. This procedure has no output.

TURN IN: A print out of your version of part2.ti that contains the procedures written for (2a), (2b) and (2c). A significant portion of the marks for this part of the assignment will be awarded according to the simplicity and elegance of your procedures.

Hint: You should study the procedure PutTableOfContents in tree.tu to get ideas about how to traverse the expression tree recursively, and how to display its structure using recursion.

The procedures in (2a) and (2b) should be recursive, because they are unnecessarily complex if done iteratively. Although the procedure in (2c) can be written quite nicely iteratively, you are to write it recursively.

• Drawing an Expression as a Tree
• Drawing an Expression as a Set of Nested Boxes
• Testing
• About this document ...