Now that you’ve seen several examples of recursion, let’s apply recursion to a few problems, similar to those on a programming exam. To help you, here is a checklist that will help you identify the most common sources of errors.

Check the Simple (Base) Cases

Does your recursive implementation begin by checking for simple base-cases? First check to see if the problem is so simple that no recursion is necessary. Recursive functions always start with the keyword if; if yours doesn’t, look carefully.

Have You Solved the Base Cases Correctly?

A surprising number of bugs in arise from incorrect solutions to the simple base-cases. If the simple cases are wrong, the rest of the function will inherit the same mistake. If you had defined factorial(0) as returning 0 instead of 1, any argument would end up returning 0.

Does Decomposition Make it Simpler?

Does your recursive decomposition make the problem simpler? Problems must get simpler as you go along; the problem must get smaller as it proceeds. If the problem does not get simpler, you have the recursive analogue of the infinite loop, which is called nonterminating or infinite recursion.

Here's the rest of the recursion checklist.

Have You Covered All Possibilities?

Does the simplification process always reach the base case, or have you left out some of the possibilities? A common error is forgetting one of the base-cases. You need to check the empty string in the isPalindrome() function, as well as the single-character string. Since the function reduces the size of the string by two each time, only having the one-character base case, would mean some strings would fail.

Are Sub-problems Identical in Form?

Are the recursive sub-problems truly identical in form to the original? It is essential that the sub-problems be of the same form. If the recursive calls change the nature of the problem then the entire process can break down.

Are You a Believer?

When you apply the recursive leap of faith, do the solutions to the recursive sub-problems provide a complete solution to the original problem? Work through all the steps in the current function call, but assume that every recursive call returns the correct answer. If this process yields the right solution, your program should work.

On the Canvas course home page, you’ll find a link to Code Step-by-Step, a Web site providing practice problems in several different programming languages, including C++. Go ahead and create your own account, and then let’s walk through a problem.

Click the C++ link as shown in the screenshot above, and then find the recursion section. Here are the instructions for the first problem, collapseSequences.

The following table shows two examples and their expected return values:

Call	Returns
collapseSequences("aabaaccaaaaaada", 'a')	"abaccada"
collapseSequences("mississssipppi", 's')	"misisipppi"

Let's walk through the steps listed in the checklist. Normally, of course, you'll compress these steps together in an intuitive way. However, if you have difficulty with solving a recursive problem, going back and checking them individually is a good debugging tool.

Check the Simple (Base) Cases

What is the simplest base case? In other words, what values for s require no compression? Well, obviously, if we don’t have any characters, there can be no compression. Similarly, if we have only a single character, there can be no compression. The simplest thing that can work, without recursion is:

string collapseSequences(const string& s, char c)
{
    if (size() < 2) return s;  // base case
}

Have You Solved the Base Cases Correctly?

Have we handled all of the base cases? The empty string returns "", and a single character returns that character. It doesn’t matter if the character matches the parameter c, since a single-character cannot be a sequence. Those should be all of the base cases. If we have two charcters, we may have a sequence "cc" that requires compression.

Does Decomposition Make it Simpler?

Does decomposition make it simpler? Or, in other words, how can we solve a simpler version of the problem? Or, how can we approach the base case? How? By passing a smaller string each time we call the function recursively.

Let's continue with the remaining steps in the checklist.

Have You Covered All Possibilities?

We have (at least) two characters, (because otherwise, we would have gone into the base case). In any event, we only need to think about the first two characters.

• They may both match c. If that is the case, then we need to ignore the first character, and pass only a shortened string to the function.
• They may not both match c. If so, them we must include the first character in the returned string before passing a shortened string to our function.

This should cover all possibilities.

Are the Subproblems Identical in Form?

Depending on whether both characters match c or not, we do a different action in each case; in one we include the first character, and in other we do not, but the form of the problem is the same in both cases.

Are You a Believer?

Walk through a solution using the simplest recursive cases. If it works for those, then it must work for all of them.

1. Call collapseSequences("vv", 'v')
• Both characters match c, so the first v is ignored and the function is called again with the string "v".
• On the second recursive call, the base case returns "v"
• Thus, the sequence "vv" is compressed to "v", so it works.
2. Now call collapseSequences("va", 'v')
• The two characters do not match, so the first 'v' is returned along with the value returned on the recursive call.
• The second recursive call returns "a" from the base case.
• Thus, the sequence "va" is not compressed (even though one of the characters matched the character c). So, it works.

Implement the algorithm described here and you'll see that all of the tests should pass. Now you can try a few problems on your own.