# 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

### 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.