Skip to main content

Section 24.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);

Insight 24.7.1.

Anytime you want to keep track of a piece of information during recursion, you can add it as an additional parameter.
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:
Listing 24.7.1.
Calling our countZeros just got more complex. main has to pass in 0 as the starting index: 
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: 
int 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 24.7.1.

We could make the countZeros function count down from the last index of the vector to the beginning. Starting that process might look like countZeros(myVector, myVector.size() - 1).
Complete the code for this version:
You have attempted of activities on this page.
PrevTopNext