## Description

Background

One of the topics that programming students have a difficult time with is the idea of recursion. The definition of a recursive function is quite simple: A recursive function is simply a function that must call itself in order to get its work done. While this definition is easy enough to understand, the ability to write good recursive code is a difficult skill to learn, and takes a lot of practice. There are two important things to keep in mind when designing a function that uses recursion:

Each time the function calls itself, that executing instance of the function maintains its own state, i.e. it contains its own unique set of local variables.

When the function returns, it returns back to the point where it was called.

Objective:

Create and test recursive functions.

Project:

Create two unrelated recursive functions, mysort and hilo. While either of these functions could be implemented iteratively, this project will assist you in mastering simple recursion.

void mysort(int nums[], int nelems)

This function sorts an array integer by finding the minimum element, swapping it with the first element, and then repeating the process on the rest of the array, recursively, until the entire array is sorted.

You will need a recursive helper function that takes three parameters: the array, the numeric index of the first element in the array (0 on the first call), and the size of the array at the moment (the number of elements in the first call). The stopping condition is an array of size 0.

The second function is:

void hilo(int size)

This function initiates a guessing game, where the user thinks of a number between 1 and size, and the program tries to guess it. It uses a binary-search-type approach, by first guessing the number in the middle of the range [1,size]. The user responds to the guess by saying whether it is too low (l), too high (h), or correct (y).

All of the work is done in the helper function, which takes the first and last numbers in the current range of possible numbers ([1,size] to start; hilo just calls the helper function with these parameters after printing an initial greeting). After the user responds, the helper function either:

quits with a success message if the guess is correct

calls itself recursively on the remaining larger numbers if the guess was too low

calls itself recursively on the remaining smaller numbers if the guess was too high

You will also need to detect if the user cheated. This is done by simply detecting whether there are no numbers left to try. The stopping condition for your helper function is, therefore, one of the following:

the user entered ‘y’

there is only one number left in the list (which should be correct)

there are no numbers left to try

Include all four functions and your main driver in a single .cpp file. Format and document your code in accordance with the course style guidelines. Include a file prologue identifying you as the author. Submit your project using the instructions outlined in the Course Syllabus, Programming Projects section.

Submitting Your Assignment

After you are satisfied that your program works correctly, submit it to Canvas as project #3. Create a zip file for this project and include the following:

The source code for your driver.

A screen shot of your execution results.

Grading Criteria

Description Points possible Your points

Your program meets the grading guidelines:

Source code files contain a declaration that you did not copy any code

Submitted to Canvas

Code meets style guidelines

Code is properly documented

5

Your program contains the mysort function and its helper function as described above.

5

Correctly sorts the array {5,4,3,2,1} as shown in the sample output below.

5

Your function, hilo(), prints a greeting and correctly calls its helper funtion to conduct the guessing game as described above and illustrated in the sample output below.

5

Your hilo helper function detects cheating and does not ask any more questions than it needs to.

5

Your hilo helper function detects invalid input and recovers gracefully.

5

– Late Penalty (20% per day)

Total 30

Sample Output:

Problem 3 output

Here is what hilo would look like if the user’s number were 50, but they lied: