Lab 4: Recursion

Topics: Recursion, Strings

Group work: Group work is allowed for the labs, but each person must do their own coding and each person must turn in an assignment. Copying other peoples' code / code files is not allowed. Copied assignments will receive 0% for everybody involved.

Assignments must build: Assignments that don't build will automatically just be given a flat 50% score. I may still give feedback on what went wrong, and 50% is better than 0%, so turn in something - but ideally, make sure it builds.


 

About

Recursion can be hard to think in terms of, especially early on. For this lab, we will step through some recursive functions, and then you will be challenged to try to design solutions for the others.

Reference the textbook, reading notes, and lectures for additional help.


Recursion

Our recursive function is a way we can implement the same functionality, but thinking of the function as only executing one step in the process. Once it's done with its one step, it calls the same function again, changing the parameters to get it ready for the next step.

Recursive functions require two parts: a Terminating Case (the scenario where the recursion will end.) and a Recursive Case (the scenario where we call the same function again, but with different arguments.)

Let's say we were adding all the numbers from 5 to 0 recursively. The way we would process the commands would be something like this...

  • What is 5 plus all the numbers until 0?
    It is 5 plus (4 plus all the numbers until 0).
    • What is 4 plus all the numbers until 0?
      It is 4 plus (3 plus all the numbers until 0).
      • What is 3 plus all the numbers until 0?
        It is 3 plus (2 plus all the numbers until 0).
        • What is 2 plus all the numbers until 0?
          It is 2 plus (1 plus all the numbers until 0).
          • What is 1 plus all the numbers until 0?
            It is 1 plus (0 plus all the numbers until 0).
            • What is 0 plus all the numbers until 0?
              Well, it's 0!
          • 1 plus (0 plus all the numbers until 0) is 1 + 0. Return 1.
        • 2 plus (1 plus all the numbers until 0) is 2 + 1. Return 3.
      • 3 plus (2 plus all the numbers until 0) is 3 + 3. Return 6.
    • 4 plus (3 plus all the numbers until 0) is 4 + 6. Return 10.
  • 5 plus (4 plus all the numbers until 0) is 5 + 10. Return 15.

15 is the result!

The statements in blue ("What is x plus (x-1 plus all the numbers until 0)?") are all places where we will recurse; we will call the same function, but with a smaller piece of data, so that we can figure out one slice of the problem at a time.

The statements in purple ("x plus (x-1 plus all the numbers until 0) is...") are places where the functions begin returning, bubbling up from the deepest function called back outward to the first function called.


 

Setting up the project

In your Student Repository, open the CS250-Lab04-Recursion project. It will have the following files:

  • main.cpp
  • functions.hpp
  • functions.cpp

This code includes function stubs and unit tests to help you check your work, as well as the base program code. When you run the program, you'll get this startup menu:

******************************
* CS 250 Lab 4     Main Menu *
******************************
1. Run tests
2. Run program
3. Quit

SELECTION: 

When you select Run tests, it will run through all the unit tests and tell you what passes and fails. If a test fails, it will tell you what it was expecting to get as the result, and what was actually returned as the result. This should help you with debugging you code.

SELECTION: 1

---------------------------------------------------
Test - Alphabet

TEST 1: Alphabet_Iter: Generate 'a' thru 'g'                           x FAIL
	 EXPECTED: "abcdefg" 
	 ACTUAL:   "NOT IMPLEMENTED"

[...]

TEST 1: Factorial_Iter: Find 0!                                        x FAIL
	 EXPECTED: "1" 
	 ACTUAL:   "-1"

[...]

TEST 1: CountConsonants_Iter: Count consonants in "aeiou"              x FAIL
	 EXPECTED: "0" 
	 ACTUAL:   "-1"

[...]

TEST 1: GetFirstUppercase_Iter: Find first consonant in "HELLO"        x FAIL
	 EXPECTED: "H" 
	 ACTUAL:   "x"

At the moment, all the function stubs have default return values, since most compilers require that functions with return-types return something.

As you implement the Iterative and Recursive versions of each function, you will be able to verify that they work right with the tests.


 

Function 1: Alphabet

string Alphabet_Iter( char start, char end );
string Alphabet_Rec( char start, char end, string text = "" );

For this function, a starting and an ending letter will be passed in. For example, 'a' and 'z'. This function will start with an empty string and build a string of letters from 'a' to 'z' (inclusive) like: "abcdefghijklmnopqrstuvwxyz".

char variables can be treated like int variables... If we have a char letter that's set to 'a', then writing letter++ will change it to 'b'.

Iterative version

Use a for loop, but use a character instead of an integer variable as your counter variable...

for ( char i = start; i <= end; char++ )

This will step you through all letters from the start to the end.

Make sure you have a string to store the list of letters in, and return that string at the end of the function.


Recursive version

Terminating Case: We're done "looping" (recursing) once we've covered all letters from start to end. You can tell we're done if start > end. (If we were getting 'a' through 'g', then it would stop when the start is 'h'.)

At this point, return the text variable, which should contain all the letters now.

Recursive Case: If we're not done recursing (the start is not yet past the end), then we need to add the next letter onto our text string, and then pass off the job to another instance of the function.

When you recurse back into Alphabet_Rec(...), you will pass in start+1, end, and text.


 

Function 2: Factorial

int Factorial_Iter( int n );
int Factorial_Rec( int n );

This function calculates n! (n-factorial). n-factorial is calculated by multiplying everything from n down to 1, so...

n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1


Iterative Version

Use a for-loop to go from n to 1, multiplying all the numbers on the way down. You will probably need an extra variable declared before the loop to store the running product.


Recursive Version

Terminating Case: If n is 0, then return 1.

Recursive Case: Otherwise, calculate n!, which is n · (n-1)!


 

Function 3: CountConsonants

int CountConsonants_Iter( string text );
int CountConsonants_Rec( string text, unsigned int pos = 0 );

This function looks at all the letters in the string, counting the amount of consonants found. There is a helper function provided in the file, bool IsConsonant( char letter ), which will return false if it detects a vowel, and true otherwise.

A string is really just a char array, and you can treat it as such. You can get the length of the string with stringname.size(). This lets you easily iterate through the string with a for-loop:

for ( unsigned int i = 0; i < text.size(); i++ )
{
    // This is just an example of how to iterate through all the letters;
    // This exact code isn't part of the solution.
    cout << "Letter " << i << " is " << text[i] << endl;
}

Iterative Version

Use a for-loop to iterate through all the letters of the string. Use the IsConsonant function, checking if it returns true or false for each letter. Any time it returns true, add 1 to a variable that stores the total amount of consonants. (It should be declared and initialized to 0 before the loop starts.)


Recursive Version

Terminating Case: If the pos equals the size of the string (text.size()), then we have no characters available in the string. Return 0.

Recursive Case: Look at whether the current character (text[pos]) is a consonant. If it is, you're going to return one plus CountConsonants_Rec( text, pos+1 ). If not, it's going to be zero plus CountConsonants_Rec( text, pos+1 ).


 

Function 4: GetFirstUppercase

char GetFirstUppercase_Iter( string text );
char GetFirstUppercase_Rec( string text, unsigned int pos = 0 );

There's a helper function for this part as well, bool IsUppercase( char letter ).


Iterative Version

Use a for loop to step through all the letters in the string. If a letter is uppercase (use the IsUppercase function), then return that letter as the result.

Otherwise, if you've completely gone through the loop and not returned any information yet, this means that there were no uppercase letters. In this case, you will return an empty char, ' ', at the end.


Recursive Version

Terminating Case:

TERMINATING CASE 1: If we're out of letters to look at (pos == text.size()), then return an empty char ' '.

TERMINATING CASE 2: If we find an uppercase letter, return it.

Recursive Case: Use a recursive function call and a return statement. You're going to recurse into GetFirstUppercase_Rec, passing in text and the next position in the string to look at.


 

Turn in

Turn in your functions.cpp file - no other files are necessary.