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)

---