# Lab Three Solution

\$30.00 \$24.90

Category:

## Description

Objectives:
The objective of this lab is to help you better understand the concept of recursion and use this concept to solve a simple programming problem.

After completing this lab, you should be able to

Explain what recursion is and how it works.
Think through a simple problem that involves recursion.
Write programs that use recursion.

What is Recursion?
Simply stated, a recursive function is a function that must call itself in order to solve a problem. A recursive function must have the following properties:

The function must have at least one base case that does what it is supposed to do without needing to calling itself.
The function must have a recursive case, where the function calls itself in order to accomplish what it is supposed to do.
There must always be a way for the function to reach its base case.

Thinking Recursively
The basic approach to solving a problem recursively is to see if we can reduce the problem to one that takes a simpler set of inputs. Most often this is a subset of the original input.
Then, consider the simplest possible subset of the original data. Figure out how you would solve the problem for this simplest case. Sometimes there is more than one simplest case.
Now, combine this simplest case with some calculation that creates a subset of the data passed to the function and then calls itself, passing this subset of the original data as the new parameter.

Example
Let’s write a recursive function that counts the number of characters in a string. Of course, we could always just use the length( ) function built into the string class, but that would be cheating. So, let’s think about how to solve this problem recursively.
Using the steps above, we know that we can always take a subset of a string using the substr( ) function. For example, given the string

string str = “apple”;

we can create a string that contains all of the characters except the first one by writing

string newStr = str.substr(1);

This call creates a substring that starts at position 1 (remember that the first character is at location zero) of the original string and contains all of the remaining characters in the original string . So, in this example, newStr would contain the string “pple”.

That takes care of the first step, being able to create a subset of the original data.

Now we need to figure out what the base case is. Remember that we can’t use the length( ) function. However, we can test the case where a string is empty. Of course, when a string is empty, its length is zero. The code to make this test and handle the base case would just be

count = 0;
if (str == “”)
return count;

Combining this with the case where we take a subset of the data, we end up with the recursive function

int countChars(String str)
{
int count = 0;
if (str == “”)
return count;
else
{
count++;// add a character to the count
return count + countChars(str.substr(1) );// function calls itself
}
}

Programming Exercise:
Using this thought process, write a recursive function that counts the number of a’s in a string. Your program should include a driver that asks the user for a string, calls the recursive function, and outputs the number of a’s it found in the string input by the user.

After you are satisfied that your program works correctly, place your project folder in a zip file and submit it to Canvas as Lab #3.