Recursive Design Practice

Section 21.6 Recursive Design Practice

Let’s try applying the recursive design process to a new function. Recall that the steps in our process are:

Identify the inputs and outputs for the function

🔗
Determine the base case for the recursion

🔗
Define the recursive case to break down the problem into a smaller version that is one step closer to the base case

🔗

🔗

Activity 21.6.1.

We want to write a function that counts the number of 0’s in a vector of integers using recursion.

🔗

(a)

What are the inputs and outputs for this function?

🔗

Input: a vector of integers, Output: the number of 0’s in the vector
Input: a vector of integers, Output: the sum of the integers in the vector
Input: a vector of integers, Output: the maximum integer in the vector

🔗

(b)

What is the best base case for this function?

🔗

If the vector is empty, return 0.
If the vector has only one element, return 1 if it is 0, otherwise return 0
This is simple in that it only involves checking a single element. But it is still more work than it could be.
If none of the elements is 0, return 0.
That is not an easy job. It still involves looking at the entire vector!

🔗

(c)

How could a recursive case for this function break down the problem into a smaller version that is one step closer to the base case?

🔗

Remember, we want to take most of the work and hand it off to “someone else” (a recursive call).

🔗

Remove the last element from the vector.
Change the last element to 0.
Our base case involves an empty vector. This does not get us closer.
Check if there are 0’s left to decide if we need to recurse again.
A recursive function case should have one simple job. In this case it should look at just one element. The reset are“someone else”’s problem.

🔗

(d)

When the recursive case gets an answer to the simpler problem, what do we do with that answer?

🔗

Return the count from the recursive call and add 1 if the last element (that we removed) is 0.
Return the count from the recursive call.
That does not include our part of the task - dealing with the last element.
Return the count from the recursive call and add 0 if the last element (that we removed) is 0.
Each we see should increase the total by 1.

🔗

Now we can put it all together. Build the working function and then test it out:

🔗

Checkpoint 21.6.1.

Build the countZeros function.

🔗

int countZeros(vector<int>& numbers) {
---
    if (numbers.empty()) {
---
        return 0;
---
    } else {
---
        int lastElement = numbers.back();
---
        numbers.pop_back(); // remove last element
---
        int count = countZeros(numbers);
---
        if (lastElement == 0) {
---
            count = count + 1;
---
        }
---
        return count;
---
    }
}

🔗

You have attempted of activities on this page.