To understand what recursion is, you must first understand recursion

Question

This is the second assignment for my CS2 course:

• Write a recursive C++ function writeLine() that writes a character repeatedly to form a line of n characters. For example:

  writeLine('*', 5)
  

  produces the output:

  *****
  

• Write a recursive [C++] function writeBlock() that uses writeLine to write m lines of n characters each. For example,

  writeBlock('*', 5, 3)
  

  produces the output:

  *****
  *****
  *****
  

• Implement and test a recursive C++ function writePyramid(). The function should take in a character to build a pyramid with and the
  height of the pyramid (the number of lines in it). Hint: Each line in the pyramid should be generated by two calls to writeLine: the first
  call generates the spaces and a second call to generate the line of
  characters. The ␣ in the output below represents a space character. This output is generated when the function is asked to generate a pyramid of height 3 with the * character.

  ␣␣*
  ␣***
  *****
  

Please feel free to rip the code apart! In my opinion, I think the switch in main() could be DRYed up a bit, but I wasn't sure how.

---

lab2.cpp:

#include <iostream>
#include <cstdio>
#include "lab2functions.h"

char getSanitizedChar()
{
  // absorb newline character (if existant) from previous input
  if('\n' == std::cin.peek()) std::cin.ignore();
  return std::tolower(std::cin.get());
}

int main()
{
  char type = '*';
  char shape = 'l';
  int rows = 0;
  int cols = 0;
  do
  {
    std::cout << "Enter shape you would like {(L)ine, (b)lock, (t)riangle}: ";
    std::cin >> shape;

    switch(shape)
    {
    case 'l':
      std::cout << "Enter number of columns: ";
      std::cin >> cols;
      std::cout << "Enter character to build with (*): ";
      type = getSanitizedChar();
      writeLine(('\n' == type ? '*' : type), cols);
      std::endl(std::cout);
      break;
    case 'b':
      std::cout << "Enter number of rows: ";
      std::cin >> rows;
      std::cout << "Enter number of columns: ";
      std::cin >> cols;
      std::cout << "Enter character to build with (*): ";
      type = getSanitizedChar();
      writeBlock(('\n' == type ? '*' : type), rows, cols);
      break;
    case 't':
      std::cout << "Enter number of rows: ";
      std::cin >> rows;
      std::cout << "Enter character to build with (*): ";
      type = getSanitizedChar();
      writePyramid(('\n' == type ? '*' : type), rows);
      break;
    default:
      std::cout << "Invalid option";
      break;
    }
    std::cout << "\nRun a calculation again (y/N): ";  // signify n as default with capital letter
  } while ('y' == getSanitizedChar());
}

lab2functions.h:

#ifndef LAB2FUNCTIONS_H
#define LAB2FUNCTIONS_H

#include <cstdint>

void writeLine(const char, const int8_t);
void writeBlock(const char, const int8_t, const int8_t);
void writePyramid(const char, const int8_t);

#endif

lab2functions.cpp:

#include <iostream>
#include "lab2functions.h" 

void writeLine(const char c, const int8_t num)
{
  if (num > 0)
  {
    std::cout << c;
    writeLine(c, num - 1);
  }
}

void writeBlock(const char c, const int8_t m, const int8_t n)
{
  if (m > 0)
  {
    writeLine(c, n);
    std::endl(std::cout);
    writeBlock(c, m - 1, n);
  }
}

void writePyramid(const char c, const int8_t h)
{
  static int count;
  count++;
  if (h > 0)
  {
    writeLine(' ', (2 * h - 1) / 2);
    writeLine(c, (2 * count - 1));
    std::endl(std::cout);
    writePyramid(c, h - 1);
  }
  count = 0;
}

Answer 1

Usually we write recursive functions with the exit condition all by itself:

void writeLine(const char c, const int8_t num)
{
  if (num > 0)
  {
    std::cout << c;
    writeLine(c, num - 1);
  }
}

I would normally write this as:

void writeLine(const char c, const int8_t num)
{
  if (num <= 0)
  {
      return;
  }

  std::cout << c;
  writeLine(c, num - 1);
}

No real reason apart from tradition I suppose. But it does show tail recursion more clearly. The compiler can easily optimize tail recursion into a loop for you. But it also makes it obvious to the human eye where tail recursion is.

A static member of a recursive function!!!

void writePyramid(const char c, const int8_t h)
{
  static int count;
  count++;

That's a bit strange. You normally pass all values as parameters between iterations. If you need a defaulting starting value then you can either use a wrapper function that calls your recursive function and provides the initial value. Or have a parameter that defaults to the start value but internally you increment it (I choose the second here).

void writePyramid(const char c, const int8_t h, int count = 0)
{
  if (h <= 0)
  {
    return;
  }

  writeLine(' ', (2 * h - 1) / 2);
  writeLine(c, (2 * count - 1));
  std::endl(std::cout);
  writePyramid(c, h - 1, count + 1); 
}

I know that Static storage duration objects are zero initialized. But how many of your peers know this. It would have been nice to give them a hint.

static int count = 0;

Going back to your wrapper code:

All the switch statements contain the same bit of code:

  std::cout << "Enter number of rows: ";
  std::cin >> rows;
  std::cout << "Enter number of columns: ";
  std::cin >> cols;
  std::cout << "Enter character to build with (*): ";
  type = getSanitizedChar();

Keep it DRY. Either move this into a separate function (called from each case). Or move it to before the switch intirally.

Answer 2

Bug! Your problem statement says

writeBlock('*', 5, 3)

produces the output:

*****
*****
*****

But your code says

void writeBlock(const char c, const int8_t m, const int8_t n)
{
  if (m > 0)
  {
    writeLine(c, n);
    std::endl(std::cout);
    writeBlock(c, m - 1, n);
  }
}

which produces output

***
***
***
***
***

To get the output specified, it should be

void writeBlock(const char c, const int8_t m, const int8_t n)
{
  if (n > 0)
  {
    writeLine(c, m);
    std::endl(std::cout);
    writeBlock(c, m, n-1);
  }
}

There's nothing wrong with writePyramid, but it is possible to make it more recursive.

void writePyramidLine(const char c, const int8_t h, const int8_t s)
{
  if ( s > 0 )
  {
    cout << ' ';
    writePyramidLine(c, h, s-1);
    cout << ' ';
  }
  else
  {
    writeLine(c, h);
  }
}

void writePyramid(const char c, const int8_t h, const int8_t s)
{
  if ( h > 0 )
  {
    writePyramid(c, h - 1, s + 1);
    writePyramidLine(c, h, s);
    std::endl(std::cout);
  }
}

void writePyramid(const char c, const int8_t h)
{
  writePyramid(c, h, 0);
}

Answer 3

I see a type mismatch for rows and cols. You have

  int rows = 0;
  int cols = 0;

in main yet all the functions to which you are passing those values -- writeLine, writeBlock, writePyramid -- have arguments of type int8_t.

I suggest changing all of those to be of same type. A better type for them would be unsigned int. Then you don't have to worry about dealing with negative numbers.

It is possible that a user will enter numbers too large for the purposes of this program. To deal with that eventuality, provide the users with appropriate feedback about the maximum admissible values. For example:

std::cout << "Enter number of rows [0-70]: ";

When you read the numbers, make sure that the user hasn't entered a number that is beyond the suggested range.

std::cin >> rows;
if ( rows > 70 )
{
    // Do something about it.
}

Since you are dealing with only integral numbers as input from users, I would create a helper function to get input from users.

unsigned int getInput(std::ostream& out,
                      std::istream& in,
                      std::string const& prompt,
                      const unsigned int& maxValue)
{
   out << prompt << " [0 - " << maxValue << "] : ";
   unsigned int number;
   in >> number;

   // Check whether read was successful.
   if ( !in )
   {
       // Clear the input stream and try to get the input again.
       in.clear();
       in.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
       return getInput(out, in, prompt, maxValue);
   }

   // Check whether the given number is below or equal to maxValue.
   if ( number > maxValue )
   {
       out << number << " is greater than the allowed maximum value, " << maxValue << ". Please try again.\n";
       return getInput(out, in, prompt, maxValue);
   }

   // All is well. The number can be returned.
   return number;
}

Then, you can use it as:

rows = getInupt(std::cout, std::cin, "Enter the number of rows", 70);

Answer 4

On how to DRY up the switch:

Remember that you can put stuff in a function and call it. In each subsection of the switch, you're finding out the number of columns and/or rows, finding out what character to use, and then using it. Whether you're interested in columns or rows or both depends on which thing you're doing, so it would make the most sense to have separate functions to get columns and to get rows.

In figuring out which character to use, you do 2 things: call getSanitizedChar() and then use it in this expression ('\n' == type ? '*' : type). You use both of these things together consistently, so it would make sense to turn the 2 separate things into a single thing. My suggestion would be this:

char getBuildChar()
{
  char ch = getSanitizedChar();
  return ('\n' == ch) 
           ? '*' 
           : ch;
}

I dislike the name type, which suggests something related to programming language types, so I've used ch (short for char) instead. Also, I used a bit of indentation to help clarify what's going on in the ternary operator slightly.

If you wrote getCols() and getRows(), you could have a cleaned up switch that looks like this:

ch = getBuildChar();

switch(shape)
{
case 'l':
  cols = getCols();
  writeLine(ch, cols);
  std::endl(std::cout);
  break;
case 'b':
  rows = getRows();
  cols = getCols();
  writeBlock(ch, rows, cols);
  break;
case 't':
  rows = getRows();
  writePyramid(ch, rows);
  break;
default:
  std::cout << "Invalid option";
  break;
}

Having the std::endl(std::cout); line after the writeLine() call is slightly ugly, but not terrible. You could write a wrapper function that calls writeLine() and then prints the newline, but the fix is about as messy as what it's fixing, so I'd probably just leave it like that. (EDIT: As pointed out in the comments, getting the character to use can be done before the switch, further reducing duplication.)

In general, if you find yourself using copy/paste to duplicate a block of code, you should probably stop, make a function out of the code, and then call the function instead.