## 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)