Lab 9: Recursion

CMSC 10600 Spring 2014

An Example: Summation

In this example, we will look at two functions to calculate the sum from 1 to n, where n is an integer:

Sum symbol

We can write a function in C++ to calculate this sum in a number of ways. The following function, called iterativeSum, calculates the sum from 1 to n iteratively. It loops through the numbers to be added and keeps a tally of the growing sum.

int iterativeSum(int n){
    
    int sum = 0;
    
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    
    return sum;
}

Now we will write a function called recursiveSum to calculate the sum recursively. Our recursive function needs the following:

a case where the value is computed by a call to the same function (a recursive call)
a base case, or a case where the value is computed without the use of a recursive call

Our recursive function is based on the following observation. To calculate the sum from 1 to n, we can write:

Sum symbol

In words, this says that the sum from 1 to n is equal to n plus the sum from 1 to n - 1. Translating this formula into C++ says that the the value of recursiveSum(n) should be the same as the value of the expression n + recursiveSum(n - 1). The definition of the function recursiveSum is given below.

int recursiveSum(int n){
    
    int sum;
    
    if (n == 1)
        sum = 1;
    else
        sum = n + recursiveSum(n - 1);
    
    return sum;
}

The case where n is equal to 1 is the base case. If n is equal to 1, then recursiveSum(n) simply returns 1.

Before Starting

Open the terminal. Go to your yourusername-cs106-spr-14 folder and make a lab9 folder using the using the commands

cd yourusername-cs106-spr-14
mkdir lab9

Today you will be writing a program to sort an array of integers recursively. Since this will only require a few functions (in addition to main()), you only need to create one cpp file called sort.cpp.

Make sure to svn add and svn commit your lab9 folder and sort.cpp.

Selection Sort

In this lab, you will write a program that recursively sorts an array of integers in ascending order (from lowest to highest). You will be using a sorting algorithm called Selection Sort. Selection Sort rearranges the values in an array a so that a[0] is the smallest, a[1] is the next smallest, and so on. It works in the following way:

the smallest value in the array is found
the smallest value is interchanged with the first value in the array

The steps are repeated until the array is sorted. The following shows and unsorted array a and a after the steps of Selection Sort.

a[0]  a[1]  a[2]  a[3]
 8     10     6    2
 2     10     6    8
 2     6      10   8
 2     6      8    10

Originally, a is the list of numbers {8, 10, 6, 2}. The first step is to place the smallest value in a[0]. The smallest value is the value in a[3], so the algorithm interchanges the values of a[0] and a[3]. The second step is to repeat this process on the values in a[1], a[2], and a[3]. The next-smallest element is in a[2], so the values in a[1] and a[2] are interchanged. Lastly, the algorithm operates on a[2], and a[3]. The smallest value is the value in a[3], so the values in a[2] and a[3] are interchanged.

Notice that the number of elements to be sorted decreases by one after each pass. Also notice that the algorithm didn't need to do anything with the value in a[3]. Once the other elements are positioned correctly, a[3] must have the correct value. You will need to use these insights to write your Selection Sort function recursively.

Your program sort.cpp should include a selectionSort function that recursively sorts an array of integers and a main function that tests selectionSort on a variety of arrays. The function declaration for selectionSort is given below.

void selectionSort(int a[], int startIndex, int endIndex);
// Precondition: the array elements a[startIndex] though a[endIndex]
// have values
// Postcondition: the array elements are sorted
// a[startIndex] <= a[startIndex + 1] <= ... <= a[endIndex]

The function selectionSort does the following:

finds the index of the smallest value in a[startIndex] through a[endIndex]
swaps the values of a[startIndex] and the value of a at the index found above
recursively calls selectionSort on a from index startIndex + 1 to endIndex

Don't forget that selectionSort also needs to include a base case.

Because of the complexity, your should write a helper function swapValues that interchanges two values and another helper function indexOfSmallest that finds the index of the smallest element in the unsorted end of the list. The function indexOfSmallest should also be a recursive function.

Execute your program with a variety of arrays to make sure it works correctly before submitting. By variety, we mean that you should make sure to call selectionSort on a list with only one element, a list with an even number of elements, a list with an odd number of elements, a list that is already in ascending order, a list that is in descending order, etc. Doing this will convince you (and us) that your program will work with any arbitrary list.

Submission

If you haven't already, svn add and svn commit what you have done this week (sort.cpp) in your lab9 folder.

How to Check your SVN Submission

Visit https://phoenixforge.cs.uchicago.edu/ and log in with your CNET ID and password.
Under "Jump to a project..." select yourusername-cs106-spr-14
From here, click on the "Repository" tab and you will be able to see the folders and files you have added and committed. You can even view the files from the website so that you can convince yourself that you have submitted the ones you want to be graded.