Insight 21.7.1.
Anytime you want to keep track of a piece of information during recursion, you can add it as an additional parameter.
Section 21.7 Parameters as Tools
You may have realized there is an issue with our
countZeros function. It is destructive. It will remove all of the values from the vector we give it. (That is why the parameter was not const).
We could modify the function to use a
const reference instead. To do this, we would have to change the code to make a copy of the starting vector, remove the last item from the copy, and pass that copy as the parameter:
int countZeros(const vector<int>& numbers) {
if (numbers.empty()) {
return 0;
} else {
int lastElement = numbers.back();
vector<int> copy = numbers; // create a copy
copy.pop_back(); // remove last element from the copy
int count = countZeros(numbers);
if (lastElement == 0) {
count = count + 1;
}
return count;
}
}
That would work, but it seems quite wasteful. To count the zero’s in
{5, 3, 0, 2, 0, 1}, we would make a copy that just had {5, 3, 0, 2, 0}, then another that had, {5, 3, 0, 2}, and so on....
Instead, we could modify the function to take an additional parameter that keeps track of the current index. Instead of always looking at the last item in the vector and then changing the vector, we will leave the vector the same, but change what index we are looking at.
This requires us to rethink all of our code. To keep track of the current index, we will need to add a parameter. It is storing a location in a vector, so we should use
size_t as the type:
int countZeros(const vector<int>& numbers, int curIndex);
Our base case can’t be “the vector is empty” any more, as the vector never changes. Instead, we need to base it on the current index. We will assume we start at index 0 and then move to 1, then 2, etc... (This is changing the order we deal with each element.) In this case, if the current index is equal to the size of the vector, there are no more items to look at and we should return 0.
if (curIndex == numbers.size()) {
return 0;
}
To implement the recursive case, we need to identify how to get one step closer to the base case. Well, if we are told to look at the vector and focus on
curIndex of 0, we can ask someone else to look at curIndex of 1 and use their answer to learn about the rest of the vector. That person would ask someone else to look at index 2. Each recursive step will increase the current index.
Here is the updated version:
countZeros(numbers, 0);
That is not the end of the world. But it does seem silly to have to pass in 0 every time we call the function. It would be nice if we could just call
countZeros(numbers) and have it work.
We can solve this by either making
curIndex have a default value:
int countZeros(const vector<int>& numbers, size_t curIndex = 0);
Or by creating a non-recursive function
countZeros which takes the vector and then calls the recursive countZeros with the correct parameters:
void countZeros(const vector<int>& numbers) {
return countZeros(numbers, 0); //start recursion with extra params
}
In the case of recursive functions with extra parameters, it is common to provide a function like this that “kick starts” the recursion. With that helper function in place, main can go back to simply call
countZeros(numbers);
Checkpoint 21.7.1.
You have attempted of activities on this page.
