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.
Purposes:
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:
     ABACABADABACABA
  */

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.
EXAMPLES: 
  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: 
0010100
0010101
0010110
0010111
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 (main@colorado.edu)