CIS 351

Homework 8: Recursion

Winter 2022

Overview

The purpose of this lab is to practice correct stack management by writing a recursive function.

Warm-up: Selection Sort

Write a function loc_of_min that returns a pointer to the minimum value in an array. Then use loc_of_min to complete selection_sort. The purpose of this exercise is to make sure you set up, use, and tear down the stack properly. The automated tests look at the stack as well as the final state of the array, so you may gets test failures, even if your code sorts the array.

Recursion: n Choose k

In probability theory "n choose k" is the number of unique ways to choose k items from a set of n. For example "5 choose 3" is 10, because there are 10 unique ways to draw three balls from a set of five (ABC, ABD, ABE, ACD, ACE, ADE, BCD, BCE, BDE, and CDE).

For this portion of lab, you are going to implement n choose k recursively using this formula: n choose k = (n-1 choose k) + (n-1 choose k-1)

n choose k is defined only for positive integers where n ≥ k. By definition

n choose 0 = 1,
n choose 1 is n, and
n choose n is 1.

Here is a test class for your function. There is no test file for the driver program. You must test it by hand.

Submission

In order to earn an 'M' or 'E' for this lab, you must use conventional register usage and stack-management techniques. Simply passing the automated tests is not sufficient.

When you are done:

Make sure your names are in the source code.
Commit with a [Grade Me] message.
Be sure to run the workflow labeled "Both"

Updated Tuesday, 22 March 2022, 4:29 PM