[SOLVED] CS-1410-project 3-Recursion

7.10 Programming Project #3:
Recursion
Background
Recursion is easy to learn but difficult to master. The definition of a recursive function is
quite simple: it’s a function that must call itself in order to get its work done and then
stop through the use of a base case. 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:
1. 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.
2. When the function returns, it returns back to the point where it was called (just
like any other function) in the previous invocation of itself.
Objective
Create and test recursive functions.
Project Requirements
Create two recursive functions, hilo and rsort. While these functions could easily be
implemented iteratively, this project will assist you in mastering simple recursion. You
can add your code for these functions to the file main.cpp below.
hilo(int n)
This function plays the high/low, binary search guessing game covered in this chapter.
It calls GuessNumber with two changes: 1) reinterpret the guesses so that ‘h’ means
the guess was too high, and ‘l’ means the guess was too low (this is the way most
people play the game), 2) modify GuessNumber to detect if any cheating has taken
place. This occurs when there is nothing left to guess.
void rsort(int nums[ ], int nelems)
This function sorts an array of integers 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. It should call a helper function, void
sorthelp(int a[ ], int start, int n), which plays a role for sort similar to
what GuessNumber does for hilo.
Here is a sample command-line execution: (the number is 30)
Think of a number between 1 and 100
I will try and guess it with your help.
Is it 50 (l,y,h)? h
Is it 25 (l,y,h)? l
Is it 37 (l,y,h)? h
Is it 31 (l,y,h)? h
Is it 28 (l,y,h)? l
Is it 29 (l,y,h)? l
Your number is 30
Sorted result:
1
2
3
4
5
Here is an example where the user cheats near the end:
Think of a number between 1 and 100
I will try and guess it with your help.
Is it 50 (l,y,h)? h
Is it 25 (l,y,h)? l
Is it 37 (l,y,h)? h
Is it 31 (l,y,h)? h
Is it 28 (l,y,h)? h
Is it 26 (l,y,h)? h
You cheated!
Sorted result:
1
2
3
4
5
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.
As always, you will need to enter all input at once in the project input window, for
example:
h
l
h
h
l
l