Lab 11

Recursion

We've given you some code with some functions to implement, to give you some practice with recursion.  These functions are going to be over lists of integers, terminated by the value -9999.

The functions I've given you (same as the ones in the prelab) are as follows:

• int length(int *)

  • An example of a recursive function with a base and recursive case.

• int sum(int *)

  • Another example of a recursive function with a base and recursive case, to show that the first one wasn't a fluke, and to give you an idea of how a simple modification can drastically change the behavior.

• void printArray(int *)

  • Mostly there for you to check whether your sort is working for extra credit, but an example where you're not just passing things back.

The functions to implement are as follows:

• int minValue(int *)

• int maxValue(int *)

• int minIndex(int *, int)

• int maxIndex(int *, int)

• void sort(int *)

You should avoid using loops wherever possible to challenge yourself, though if one shows up in a good implementation for sort that's okay.

• • Stage 1 (1 point):

  • Implement minValue and maxValue.  minValue should return the value of the minimal element of the array, maxValue should return the value of the maximal element of the array.

  • Stage 2 (1 point):

  • Implement minIndex and maxIndex.  minIndex should return the index of the minimum element of the array, maxIndex should return the index of the maximal element of the array.  There won't be any duplicate numbers, but if there were you would return the index of the first minimal/maximal element.

  • Stage 3 (Extra Credit) (1 point):

  • Implement a sort function, which sorts the array of ints.  You should strive to make your solution as recursive as possible.

Notes:

• Keep in mind that this is a team effort so you should agree with your partner on what you are going to do before you start typing. The partner who is typing is the "driver" and the partner watching is the "navigator."  Be sure to switch roles every 10 to 15 minutes, to foster a deep understanding of the code for both partners.  The navigator should be watching for syntax errors and verifying the correctness of the code you're writing.  

• It will speed things up for you if you keep a window open for editing and have a separate window open for compiling and running your program.  Remember that windows are resizable!

Submission:

1. You should work with a partner for this (and all the remaining) lab(s).  Only one of you need to submit the program to Blackboard, though you should be certain that both of your names be present in a comment at the top of the .c or .cpp source file.

1.5 If you work alone, include just your name in a comment at the top so that I know you worked alone, and not have to guess.

2. You should turn in to Blackboard by the END OF THE LAB.  I know it's tempting to keep working on it, but other classes come in, and it's not fair to the students who are limited to that particular time span if you go over.  Which isn't to say that you can't work on it later, to check your solution against the one I post for your own understanding.  But what you submit for a grade should be before the next hour begins.

3. If you wish, you may submit your lab by noon on Friday for a 1 point penalty.  If you can't finish up the second point by the end of lab, you can still earn the score by completing all three steps and submitting your code by the day after.