Data Structures - Chapter 9 - Programming Assignment
Implement and Test Four Short Recursive Functions
(Version 2)

Data Structures and Other Objects Using C++
Second Edition
by Michael Main and Walter Savitch
ISBN 0-201-70297-5, Softcover, 816 pages

The Assignment:
You will implement and test four short recursive functions. With the proper use of recursion, none of these function should require more than a dozen lines of code. If you have an easy time with this assignment, then after you submit it you should consider doing the additional honors assignment.
Ensure that you can write and test small recursive functions.
Before Starting:
Read all of Chapter 9, especially Sections 9.1 and 9.2.
Due Date:
File that you must write:
  1. rec_fun.cxx: This file should contain the implementations of the four functions described below. You might also want to put the functions prototypes in a separate file rec_fun.h and write a test program that includes rec_fun.h.

Implement and Test Four Small Recursive Functions

1. A Pattern of Letters

  void letters(ostream& outs, char c)
  // Precondition: c is one of the characters 'A' through 'Z'.
  // Postcondition: The function has printed a pattern of letters to the
  // ostream out, as follows:
  // 1. If the parameter c is 'A', then the output is 'A'.
  // 2. For other values of c, the output consists of three parts:
  //    -- the output for the previous letter (c-1);
  //    -- followed by the letter c itself;
  //    -- followed by a second copy of the output for the previous letter.
  // There is no '\n' printed at the end of the output.
  /* Example output:
     letters(cout, 'D') will print this to cout:

2. One Binary Number

Write a function with this prototype:
  void binary_print(ostream& outs, unsigned int n);
The function prints the value of n as a BINARY number to the ostream outs. If n is zero, then a single zero is printed; otherwise no leading zeros are printed in the output. The '\n' character is NOT printed at the end of the output.
  n=0  Output:0
  n=4  Output:100
  n=27 Output:11011
NOTE: Your recursive implementation must not use any local variables.

3. Sequence of Binary Numbers

Write a function with this prototype:
  #include <strclass.h>
  void numbers(ostream& outs, const String& prefix, unsigned int k);
The argument called prefix is a String of 0's and 1's. The function prints a sequence of binary numbers to the ostream outs. Each output number consists of the prefix followed by a suffix of exactly k more binary digits (0's or 1's). All possible combinations of the prefix and some k-digit suffix are printed. As an example, if prefix is the string "00101" and levels is 2, then the function would print the prefix followed by the 4 possible suffixes shown here:
The stopping case occurs when k reaches zero (in which case the prefix is printed once by itself followed by nothing else).

The String class from <strclass.h> has many manipulation functions, but you'll need only the ability to make a new string which consists of prefix followed by another character (such as '0' or '1'). This can be done with the String expression (prefix + '0') or (prefix + '1'). This new String (with an extra '0' or '1' at the end) can be passed as a parameter to recursive calls of the function.

4. A Fractal Pattern

Examine this pattern of asterisks and blanks, and write a recursive function that can generate patterns such as this:
* * 
* * * *
    * *
* * * * * * * *
        * *
        * * * *
            * *
With recursive thinking, the function needs only seven or eight lines of code (including two recursive calls). Your prototype should look like this:
  void pattern(ostream& outs, unsigned int n, unsigned int i);
  // Precondition: longest is a power of 2 greater than zero.
  // Postcondition: A pattern based on the above example has been
  // printed to the ostream outs. The longest line of the pattern has
  // n stars beginning in column i of the output. For example,
  // The above pattern is produced by the call pattern(cout, 8, 0).
Hints: You do not need to check the precondition. Think about how the pattern is a fractal. Can you find two smaller versions of the pattern within the large pattern? Here is some code that may be useful within your function:
  // A loop to print exactly i spaces:
  for (k = 0; k < i; k++) outs << ' ';
  // A loop to print n asterisks, each one followed by a space:
  for (k = 0; k < n; k++) outs << "* ";

Michael Main (