Recursion

Table of Contents


c2_u18_Recursion_recursionB.png

1. Examples of recursion in math

Recursion is a manner of solving a problem by breaking it down into smaller pieces - and those smaller pieces are solved in the same way as the big-picture version.

1.1. Summation:

A summation can be broken down into smaller chunks but using the same structure as the original.

Let's say we have \[ \sum_{i=1}^{6} { i } = 1 + 2 + 3 + 4 + 5 + 6 \]

The summation can be redefined recursively:

\[ \sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i } \]

The summation from \(i = 1\) to \(6\) is equivalent to whatever the sum is at \(i=6\), plus the sum from \(i = 1\) to \(5\). We can continue this way until we get to a case that we know (e.g., \(\sum_{i=1}^{1} { i }\)).

  • \(\sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i }\)
  • \(\sum_{i=1}^{5} { i } = 5 + \sum_{i=1}^{4} { i }\)
  • \(\sum_{i=1}^{4} { i } = 4 + \sum_{i=1}^{3} { i }\)
  • \(\sum_{i=1}^{3} { i } = 3 + \sum_{i=1}^{2} { i }\)
  • \(\sum_{i=1}^{2} { i } = 2 + \sum_{i=1}^{1} { i }\)
  • We know that \(\sum_{i=1}^{1} { i } = 1\), then we move back up to sub out this value.
Recursive problem Finding the solution
A. \[\sum^{6}_{i=1} { i } = 6 + \sum_{i=1}^{5} { i }\] But what is \(\sum_{i=1}^{5} { i }\)? \(\downarrow\) K. DONE! \[\sum_{i=1}^{6} { i } = 6 + \sum_{i=1}^{5} { i } = 6 + 15 = 21\]
B. \[\sum_{i=1}^{5} { i } = 5 + \sum_{i=1}^{4} { i }\] But what is \(\sum_{i=1}^{4} { i }\)? \(\downarrow\) J. \(\uparrow\) \[\sum_{i=1}^{5} { i } = 5 + \sum_{i=1}^{4} { i } = 5 + 10 = 15\]
C. \[\sum_{i=1}^{4} { i } = 4 + \sum_{i=1}^{3} { i }\] But what is \(\sum_{i=1}^{3} { i }\)? \(\downarrow\) I. \(\uparrow\) \[\sum_{i=1}^{4} { i } = 4 + \sum_{i=1}^{3} { i } = 4 + 6 = 10\]
D. \[\sum_{i=1}^{3} { i } = 3 + \sum_{i=1}^{2} { i }\] But what is \(\sum_{i=1}^{2} { i }\)? \(\downarrow\) H. \(\uparrow\) \[\sum_{i=1}^{3} { i } = 3 + \sum_{i=1}^{2} { i } = 3 + 3 = 6\]
E. \[\sum_{i=1}^{2} { i } = 2 + \sum_{i=1}^{1} { i }\] But what is \(\sum_{i=1}^{1} { i }\)? \(\downarrow\) G. \(\uparrow\) \[\sum_{i=1}^{2} { i } = 2 + \sum_{i=1}^{1} { i } = 2 + 1 = 3\]
F. \[\sum_{i=1}^{1} { i } = 1\] \(\uparrow\)
Now we start substituting this value, from bottom-up… \(\rightarrow\) \(\uparrow\)

1.2. Factorials:

With a factorial of \(n\), written \(n!\) the formula to solve this is:

\[ n! = n \cdot (n-1) \cdot ... \cdot 3 \cdot 2 \cdot 1 \]

So,

  • \(2!\) is \(2 \cdot 1\),
  • \(3!\) is \(3 \cdot 2 \cdot 1\),
  • \(4!\) is \(4 \cdot 3 \cdot 2 \cdot 1\), and so on.

Additionally, we can break down each of these equations: \(3!\) is equivalent to \(3 \cdot 2!\) \(4!\) is equivalent to \(4 \cdot 3!\) … \(n!\) is equivalent to \(n \cdot (n-1)!\)

Thinking of breaking down the problem here in this way is looking at it recursively.

c2_u18_Recursion_recursivefactorial.png

2. Recursion in programming

In programming, we usually approach problems iteratively, using a for-loop or a while-loop:

// Iterative solution
int Sum( int n )
{
    int result = 0;
    for ( int i = 1; i <= n; i++ )
    {
        result += i;
    }
    return result;
}

Which solves this summation:

\[ \sum_{i=1}^n {i} \]

But some types of problems lend themselves better to a recursive solution. To be fair, though, many problems are better solved iteratively. So how do we know which method is better?


2.1. Recursion basics

When defining a problem recursively in programming, we need two things:

  1. A terminating case: A case that ends our recursing. Often, this is some known data, something hard-coded. For example with our summation, the terminating case would be that \[ \sum_{i=1}^1 {i} = 1 \] or for a factorial, \(1! = 1\) and \(0! = 1\).
  2. A recursive case: A recursive case is what happens otherwise - if we're not to a solution yet (via the terminating case), we call the same function again, but with updated arguments. For example:
    • Factorial( 4 ) = 4 * Factorial( 3 )
    • Factorial( 3 ) = 3 * Factorial( 2 )
    • Factorial( 2 ) = 2 * Factorial( 1 )
    • Factorial( 1 ) = 1

We can solve these basic math operations both iteratively and recursively:

// Iterative solution
int FactorialI( int n )
{
    int result = 1;
    for ( int i = 1; i <= n; i++ )
    {
        result *= i;
    }
    return result;
}
// Recursive solution
int FactorialR( int n )
{
    if ( n == 1 || n == 0 ) { return 1; }
    return n * FactorialR( n-1 );
}

2.2. Breaking down problems into recursive solutions

c2_u18_Recursion_recursionstress.png

One of the most challenging parts of recursion, at least for me, is trying to break away from thinking of something in terms of "looping" and figuring out how to think of it "recursively". It's not as natural-feeling, so don't worry if it's confusing at first.

Let's tackle some basic design problems to practice.

Summation:
Try to convert the Summation function to be recursive. Think about what the terminating case would be and the recursive case. Use the Factorial function for reference.
int SumI( int n )
{
    int result = 0;
    for ( int i = 1; i <= n; i++ )
    {
        result += i;
    }
    return result;
}
int SumR( int n )
{
    // Terminating case?
    // Recursive case?
}
Solution for recursive summation:
int SumR( int n )
{
    if ( n == 1 ) { return 1; }  // Terminating case
    return n + SumR( n-1 );      // Recursive case
}

Draw a line:
Now let's make a function that will draw a line of symbols, with a parameter being the length. Iteratively, it could look like this:
void DrawLineI( int amount )
{
    for ( int i = 0; i < amount; i++ )
    {
        cout << "-";
    }
}

How would we repeat this behavior recursively? How do we have a "count up" sort of functionality? What would be the terminating case?

We're going to think of it a little differently: The recursive function will only output one "-" before it recurses. Each time it recurses, it draws one more dash…

void DrawLine_Recursive( int amount )
{
    cout << "-";
    // Recursive case
    DrawLineR( amount );
}

However, we don't have a terminating case… it will continue looping, but it won't go forever like a bad while loop. We will eventually run out of stack space and the program will encounter a stack overflow and end.

So what would the terminating case be? How do we adjust the amount each time? Since amount is the one parameter we have, let's have the recursion stop once it is 0. Each time we recurse, we can pass in amount-1 to the next call…

void DrawLine_Recursive( int amount )
{
    cout << "-";

    // Terminating case
    if ( amount == 0 ) { return; }

    // Recursive case
    DrawLineR( amount - 1 );
}

Counting Up:
How can we write a function that takes a start and end integer, and outputs each number between them (including the start and end)?

Iteratively, it could look like this:

void CountUpI( int start, int end )
{
    for ( int i = start; i <= end; i++ )
    {
        cout << i << "\t";
    }
}

Try to fill in this function to build a recursive solution:

void CountUpR( int start, int end )
{
}

Solution for recursive count up:
void CountUpR( int start, int end )
{
    cout << start << "\t";

    // Terminating case
    if ( start == end ) { return; }

    // recursive case
    CountUp_Recursive( start+1, end );
}

2.3. A case for recursion

Although there are a lot of problems we could convert from an iterative solution to a recursive solution, there are some types of problems that really are better suited to recursion.

2.3.1. Searching a File System

c2_u18_Recursion_filesystem.png

On a harddrive, we generally have files and folders. Folders can contain files, but they will also contain subfolders as well. And subfolders can each contain their own subfolders.

When you don't know the exact layout of the filesystem, how would you even begin to iteratively search for a specific file?

Instead, it is good to think of it recursively. For example, say we're searching for a folder where you store your Recursion homework. We will begin searching at the top-most folder of the computer. The algorithm would then run like…

1. folder = "C:", 2. folder = "work", 3. folder = "C:"
c2_u18_Recursion_traverse1.png c2_u18_Recursion_traverse2.png c2_u18_Recursion_traverse1.png
Is this "Recursion"? No. Is this "Recursion"? No. Are there subfolders? Yes.
Are there subfolders? Yes. Are there subfolders? No. Then, search next subfolder.
Then, search first subfolder. Return.  
4. folder = "school" 5. folder = "cs210" 6. folder = "school"
c2_u18_Recursion_traverse3.png c2_u18_Recursion_traverse4.png c2_u18_Recursion_traverse5.png
Is this "Recursion"? No. Is this "Recursion"? No. Are there subfolders? Yes.
Are there subfolders? Yes. Are there subfolders? No. Then, search next subfolder.
Then, search next subfolder. Return.  
7. folder = "cs235" 8. 9.
c2_u18_Recursion_traverse6.png c2_u18_Recursion_traverse8.png c2_u18_Recursion_traverse9.png
Is this "Recursion"? No. folder = "Recursion" folder = "cs235"
Are there subfolders? Yes. Is this "Recursion"? Yes. Return Recursion.
Then, search the first subfolder. Return Recursion.  
10. folder = "school" 11. folder = "C:"  
c2_u18_Recursion_traverse10.png c2_u18_Recursion_traverse11.png  
Return Recursion. Return Recursion.  

For find functionality, terminating cases would be:

  1. Have we found the item? Return it.
  2. Are we out of places to search? Return nothing.

And the recursive case would be:

  1. Has a subfolder? Call Find() on that folder.

2.3.2. Solving a maze

Solving a maze can be approached from a recursive standpoint much easier than an iterative one.

Terminating case: If we hit a dead-end, or if we find the end of the maze.

Recursive case: Explore each available direction.

1. c2_u18_Recursion_maze.png Starting point. We will iterate through all directions we can go. In some cases, there is only one valid direction.
2. c2_u18_Recursion_maze1.png Once we hit multiple options, we will recurse into a direction. If we end up returning unsuccessfully, we will recurse into the other direction.
3. c2_u18_Recursion_maze2.png If we hit a dead-end, this is a terminating case and we begin returning.
4. c2_u18_Recursion_maze.png We get back to a previous function call where we can continue recursing in a different direction.
5. c2_u18_Recursion_maze.png Hitting a terminating case and returning backwards essentially "undoes" the path that takes us to a dead-end.
6. c2_u18_Recursion_maze.png The recursion ends once we either run out of all potential paths to take, or we achieve the goal.

3. Practice problems

Implement an iterative (looping-based) and recursive solution for each of the following.

You can also download the code files here:

1. Alphabet

This function takes in a letter start and a letter end and will generate a string with all the letters between those two values. (e.g., for Alphabet_Iter( 'A', 'D' ) will return "ABCD".)

/**
   @param      char        start       The starting char (inclusive) to begin at
   @param      char        end         The end char (inclusive) to run until
   @return     string                  A string containing all the letters from start to end.
*/
//! Build a string that contains letters from start to end.
string Alphabet_Iter( char start, char end )
{
  return "NOT IMPLEMENTED"; // Temporary
}

/**
   @param      char        start       The starting char (inclusive) to begin at
   @param      char        end         The end char (inclusive) to run until
   @return     string                  A string containing all the letters from start to end.
*/
//! Build a string that contains letters from start to end.
string Alphabet_Rec( char start, char end, string text /* = "" */ )
{
  // Terminating Case:
  // Out of letters to go over (in other words, start > end).

  // Recursive case:
  // Add the next letter, then call return and recurse into this function using the next letter.

  return "NOT IMPLEMENTED"; // Temporary
}

// Unit test function
void Test_Set1()
{
  //string Alphabet_Iter( char start, char end )
  cout << endl << "---------------------------------------------------" << endl;
  cout << "Test - Alphabet" << endl;
  string expectedOut, actualOut;

  cout << endl << left << setw( headerWidth ) << "TEST 1: Alphabet_Iter: Generate 'a' thru 'g'" << setw( pfWidth );
  expectedOut = "abcdefg";
  actualOut = Alphabet_Iter( 'a', 'g' );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }


  cout << endl << left << setw( headerWidth ) << "TEST 2: Alphabet_Iter: Generate 'l' thru 'p'" << setw( pfWidth );
  expectedOut = "lmnop";
  actualOut = Alphabet_Iter( 'l', 'p' );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }


  cout << endl << left << setw( headerWidth ) << "TEST 3: Alphabet_Rec: Generate 'a' thru 'g'" << setw( pfWidth );
  expectedOut = "abcdefg";
  actualOut = Alphabet_Rec( 'a', 'g' );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }


  cout << endl << left << setw( headerWidth ) << "TEST 4: Alphabet_Rec: Generate 'l' thru 'p'" << setw( pfWidth );
  expectedOut = "lmnop";
  actualOut = Alphabet_Rec( 'l', 'p' );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

}

2. Factorial These functions should take in some input n and generate the result of n!.

/**
   Factorial functions
   @param      int     n       The value of n
   @return     int             The value of n!

   Calculate n! by multiplying n * (n-1) * (n-2) * ... * 3 * 2 * 1.
*/
//! Calculates n!
int Factorial_Iter( int n )
{
  return -1; // Temporary
}

/**
   Factorial functions
   @param      int     n       The value of n
   @return     int             The value of n!

   Calculate n! by multiplying n * (n-1) * (n-2) * ... * 3 * 2 * 1.
*/
//! Calculates n!
int Factorial_Rec( int n )
{
  // Terminating case:
  // n is 0.

  // Recursive case:
  // n is greater than 0.

  return -1; // Temporary
}

// Unit test function
void Test_Set2()
{
  // int Factorial_Iter( int n );
  cout << endl << "---------------------------------------------------" << endl;
  cout << "Test - Factorial" << endl;
  int expectedOut, actualOut;

  cout << endl << left << setw( headerWidth ) << "TEST 1: Factorial_Iter: Find 0!" << setw( pfWidth );
  expectedOut = 1;
  actualOut = Factorial_Iter( 0 );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

  cout << endl << left << setw( headerWidth ) << "TEST 2: Factorial_Iter: Find 5!" << setw( pfWidth );
  expectedOut = 120;
  actualOut = Factorial_Iter( 5 );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

  cout << endl << left << setw( headerWidth ) << "TEST 3: Factorial_Rec: Find 0!" << setw( pfWidth );
  expectedOut = 1;
  actualOut = Factorial_Rec( 0 );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

  cout << endl << left << setw( headerWidth ) << "TEST 4: Factorial_Rec: Find 5!" << setw( pfWidth );
  expectedOut = 120;
  actualOut = Factorial_Rec( 5 );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }
}

3. Count consonants This function should iterate through the input string text and for each character, if that char is a consonant, add 1 to a counter. Return the total amount of consonants at the end.

//! Helper function to find whether something is a consonant or not.
bool IsConsonant( char letter )
{
  if (    tolower( letter ) == 'a' ||
          tolower( letter ) == 'e' ||
          tolower( letter ) == 'i' ||
          tolower( letter ) == 'o' ||
          tolower( letter ) == 'u'
          )
    {
      return false;
    }

  return true;
}

/**
   CountConsonants functions
   @param  string  text        The text to count the consonants within
   @return int                 The amount of consonants found

   Iterate through each char in the string [text] and count up 1 if that letter is a consonant.
   Return the amount of consonants found.
*/
//! Count the amount of consonants in a string and return the count.
int CountConsonants_Iter( string text )
{
  return -1; // Temporary
}

/**
   CountConsonants functions
   @param  string  text        The text to count the consonants of
   @param  int     pos         The current position being investigated
   @return int                 The amount of consonants found

   Recurse through each char in the string [text] and count up 1 if that letter is a consonant.
   Return the amount of consonants found.
*/
//! Count the amount of consonants in a string and return the count.
int CountConsonants_Rec( string text, unsigned int pos /* = 0 */ )
{
  // Terminating case:
  // No more letters to look at.

  // Recursive case:
  // Still more letters to inspect.

  return -1; // Temporary
}

// Unit test function
void Test_Set3()
{
  // int CountConsonants_Iter( string text )
  cout << endl << "---------------------------------------------------" << endl;
  cout << "Test - CountConsonants" << endl;
  int expectedOut, actualOut;

  cout << endl << left << setw( headerWidth ) << "TEST 1: CountConsonants_Iter: Count consonants in \"aeiou\"" << setw( pfWidth );
  expectedOut = 0;
  actualOut = CountConsonants_Iter( "aeiou" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

  cout << endl << left << setw( headerWidth ) << "TEST 2: CountConsonants_Iter: Count consonants in \"jkl\"" << setw( pfWidth );
  expectedOut = 3;
  actualOut = CountConsonants_Iter( "jkl" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

  cout << endl << left << setw( headerWidth ) << "TEST 3: CountConsonants_Iter: Count consonants in \"hellothere\"" << setw( pfWidth );
  expectedOut = 6;
  actualOut = CountConsonants_Iter( "hellothere" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }



  cout << endl << left << setw( headerWidth ) << "TEST 4: CountConsonants_Rec: Count consonants in \"aeiou\"" << setw( pfWidth );
  expectedOut = 0;
  actualOut = CountConsonants_Rec( "aeiou" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

  cout << endl << left << setw( headerWidth ) << "TEST 5: CountConsonants_Rec: Count consonants in \"jkl\"" << setw( pfWidth );
  expectedOut = 3;
  actualOut = CountConsonants_Rec( "jkl" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

  cout << endl << left << setw( headerWidth ) << "TEST 6: CountConsonants_Rec: Count consonants in \"hellothere\"" << setw( pfWidth );
  expectedOut = 6;
  actualOut = CountConsonants_Rec( "hellothere" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

}

4. Get First Uppercase These functions should return the first uppercase letter (a char) within the given string (string text).

//! Helper function to figure out if letter is upper-case
bool IsUppercase( char letter )
{
  return ( letter != ' ' && toupper( letter ) == letter );
}

/**
   @param  string  text    The text to look for capital letters in
   @return char            The first upper-case character found, or ' ' if none found.

   Iterate through each char in the string [text] and return the char if it is an upper-case letter.
   If no upper-case letters are found, return a space character: ' '
*/
//! Returns the first uppercase letter found, or ' ' if none are found.
char GetFirstUppercase_Iter( string text )
{
  return 'x'; // Temporary
}

/**
   @param  string  text    The text to look for capital letters in
   @param  int     pos     The current position being investigated
   @return char            The first upper-case character found, or ' ' if none found.

   Recurse through each char in the string [text] and return the char if it is an upper-case letter.
   If no upper-case letters are found, return a space character: ' '
*/
//! Returns the first uppercase letter found, or ' ' if none are found.
char GetFirstUppercase_Rec( string text, unsigned int pos /* = 0 */ )
{
  // Terminating case:
  // No more letters to look at, OR
  // First uppercase letter found.

  // Recursive case:
  // Still more letters to investigate

  return 'x'; // Temporary
}

// Unit test function
void Test_Set4()
{
  //char GetFirstUppercase_Iter( string text )
  cout << endl << "---------------------------------------------------" << endl;
  cout << "Test - GetFirstUppercase" << endl;
  char expectedOut, actualOut;

  cout << endl << left << setw( headerWidth ) << "TEST 1: GetFirstUppercase_Iter: Find first consonant in \"HELLO\"" << setw( pfWidth );
  expectedOut = 'H';
  actualOut = GetFirstUppercase_Iter( "HELLO" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }


  cout << endl << left << setw( headerWidth ) << "TEST 2: GetFirstUppercase_Iter: Find first consonant in \"heLLO\"" << setw( pfWidth );
  expectedOut = 'L';
  actualOut = GetFirstUppercase_Iter( "heLLO" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }


  cout << endl << left << setw( headerWidth ) << "TEST 3: GetFirstUppercase_Iter: Find first consonant in \"hello\"" << setw( pfWidth );
  expectedOut = ' ';
  actualOut = GetFirstUppercase_Iter( "hello" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }



  cout << endl << left << setw( headerWidth ) << "TEST 4: GetFirstUppercase_Rec: Find first consonant in \"HELLO\"" << setw( pfWidth );
  expectedOut = 'H';
  actualOut = GetFirstUppercase_Rec( "HELLO" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }


  cout << endl << left << setw( headerWidth ) << "TEST 5: GetFirstUppercase_Rec: Find first consonant in \"heLLO\"" << setw( pfWidth );
  expectedOut = 'L';
  actualOut = GetFirstUppercase_Rec( "heLLO" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }


  cout << endl << left << setw( headerWidth ) << "TEST 6: GetFirstUppercase_Rec: Find first consonant in \"hello\"" << setw( pfWidth );
  expectedOut = ' ';
  actualOut = GetFirstUppercase_Rec( "hello" );

  if ( actualOut == expectedOut )     { cout << " * PASS" << endl; }
  else                                { cout << " x FAIL\n\t EXPECTED: \"" << expectedOut << "\" \n\t ACTUAL:   \"" << actualOut << "\"" << endl; }

}

3.1. Answers

1. Alphabet

string Alphabet_Iter( char start, char end )
{
  string generated = "";
  for ( char i = start; i <= end; i++ )
    {
      generated += i;
    }
  return generated;
}

string Alphabet_Rec( char start, char end, string text /* = "" */ )
{
  if ( start > end )
    {
      return text;
    }

  return text + start + Alphabet_Rec( start+1, end );
}

2. Factorial

int Factorial_Iter( int n )
{
  int result = 1;
  for ( int i = n; i >= 1; i-- )
    {
      result *= i;
    }
  return result;
}

int Factorial_Rec( int n )
{
  if ( n == 0 )
    {
      return 1; // 0! = 1
    }

  return n * Factorial_Rec( n-1 );
}

3. Count consonants

int CountConsonants_Iter( string text )
{
  int consCount = 0;
  for ( size_t i = 0; i < text.size(); i++ )
    {
      if ( IsConsonant( text[i] ) )
        {
          consCount++;
        }
    }
  return consCount;
}

int CountConsonants_Rec( string text, unsigned int pos /* = 0 */ )
{
  if ( pos >= text.size() )
    {
      return 0;
    }

  return IsConsonant( text[pos] ) + CountConsonants_Rec( text, pos+1 );
}

4. Get First Uppercase

char GetFirstUppercase_Iter( string text )
{
  for ( size_t i = 0; i < text.size(); i++ )
    {
      if ( IsUppercase( text[i] ) )
        {
          return text[i];
        }
    }
  return ' '; // nothing found
}

char GetFirstUppercase_Rec( string text, unsigned int pos /* = 0 */ )
{
  if ( pos >= text.size() )
    {
      return ' ';
    }
  if ( IsUppercase( text[pos] ) )
    {
      return text[pos];
    }

  return GetFirstUppercase_Rec( text, pos+1 );
}

Author: Rachel Wil Sha Singh

Created: 2023-10-30 Mon 11:09

Validate