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: 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:

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.




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

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.