Assignment 3

Due date:

Late assignments will be penalized 10% per day, and will not be accepted after .

1. Hand In

Each student is required to do this assignment individually and to hand in the following:

A disk containing only two files: the source listing and executable for the program in the assignment.
Printouts of the program and the output it produces in test data of your own choice.

Place these items in a 9"x11" envelope, with the following information clearly marked on the outside of the envelope:

Name, Student Number, Assignment Number, Course Number (T26)

Assignments which are not in an envelope will not be marked

Deposit your envelope in .

Marking Scheme

Programming standards: 10pt, Each question: 10pt.

Your program must conform to the programming standards. These are described in a separate sheet.

2. Program Handout

In this assignment, all functions must be implemented using recursion rather than iteration. When you are asked to write a recursive function - let's call it foo - you are expected to devise a recursive algorithm and code foo to use this algorithm. Typically, you'll two choices:

Either directly code foo so that it calls itself recursively.
Or, code foo so that it calls an auxiliary function, say foo_aux, that is recursive and does all the interesting work. You might choose this option when the initial values for the recursive algorithm are not identical to foo's initial parameters; or, more generally, when initializations are required before starting the algorithm, or when you need to clean up after it finishes.

For questions 3 and 4, you will be given the binary, not the source, for an implementation of four list operations: is_empty, head, tail, and read_list specified below. You can link these into your program, but there is no way for you to know how lists are implemented. The specification tells you all you need to know to use these operations.

is_empty

Input: L, a list
Preconditions: L is defined
Postconditions: true if L is empty, false otherwise

head

Input: L, a list
Output: V, an integer
Preconditions: L is not empty
Postconditions: V is the first value in L. L is unchanged

tail

Input: L, a list
Output: T, a list
Preconditions: L is not empty
Postconditions: T is identical to L except it is missing L's first element

read_list

Input: none
Output: L, a list
Preconditions: the current input line contains 0 or more integers
Postconditions: L contains all the integers on the current input line, in the same order they appear. The input line is consumed.

For question 2, you may use any implementation of stack you choose.

3. Question 1

Suppose the array X has 10 elements, and we call the array addup function described in class with these arguments: addup(0,9,X).

what is the maximum depth of the function calls that will result from this? (this call itself counts as depth = 1)
what is the maximum amount of local memory (for parameters and local variables) that will be allocated at any one time during the course of computing the answer to addup(0,9,X)?

4. Question 2

Write a recursive function copy(S,Scopy) that makes a copy of the given stack S. copy must leave S unchanged - to verify this, write a function called copy_test that reads in S, calls copy, and then prints out S and Scopy.

Use the main program you are given exactly as it is (it calls copy_test).

5. Question 3

Using the head and tail functions provided, write a recursive function smallest(L) that returns the smallest integer in the given list, L. You may assume L is not empty.

6. Question 4

Write a recursive function called nth(N,L), where N is an integer, L a list. If L contains N (or more) elements, then the function returns the Nth one from the beginning (the first element is L's head). If L contains fewer than N elements, the function returns the last element in L.