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
