Programming Assignment 5  (Chapter 9) - Recursive Thinking

Adapted from Data Structures and Other Objects Using C++

by Michael Main and Walter Savitch

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.

Purposes:

Ensure that you can write and test small recursive functions.

Before Starting:

Read all of Chapter 9, especially Sections 9.1 and 9.3.

Due Date:

Wednesday, November 12, 2014. If you have problems, late work will be accepted on Tursday with no penalties. Late work may be submitted on Friday or Saturday with 5% penalty per day. No work will be accepted after Saturday.

How to Turn In:

Please submit homeworks using this link. On the upload page, you can select the file(s) you want to submit (multiple files can be selected by pressing down CTRL key while selecting the files). Then enter your last name and the last 4 digit of your student ID (from CUNYfirst, NOT your SSN!!!). Once successfully submitted, it will show a page with RECEIPT NUMBER, save that number or that page because you will need it to retrieve your grade for that assignment. You can submit your assignment as many times as you want before the deadline, only the latest one will be graded.

To retrieve your grade for an assignment (after I finish grading it), please go to the download page here, select the assignment, enter the receipt number for that assignment, your last name and your last 4 digit of your student ID. The page will then download a TXT file which contain your graded submission.

Files that you must write and turn in:

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.

1. One Binary Number

  void binary_print(ostream& outs, unsigned int n);

  n=0  Output:0
  n=4  Output:100
  n=27 Output:11011

2. Triangle Pattern

  void triangle(ostream& outs, unsigned int m, unsigned int n)
  // Precondition: m <= n
  // Postcondition: The function has printed a pattern of 2*(n-m+1) lines
  // to the output stream outs. The first line contains m asterisks, the next 
  // line contains m+1 asterisks, and so on up to a line with n asterisks.
  // Then the pattern is repeated backwards, going n back down to m.
  /* Example output:
     triangle(cout, 3, 5) will print this to cout:
     ***
     ****
     *****
     *****
     ****
     ***
  */

3. Pow Function (Project 13, page 452)

    double pow(double x, int n);
    // Precondition: If x is zero, then n must be positive.
    // Postcondition: The value returned is x raised to the power n.

Hint: use the formula x^2n = x^n  x^n

4.  Repeated and Indented Sentences (Project 1, page 450)

Write a  function that produces output like the following:

This was written by calling number 1.
  This was written by calling number 2.
    This was written by calling number 3.
      This was written by calling number 4.
      This was ALSO written by calling number 4.
    This was ALSO written by calling number 3.
  This was ALSO written by calling number 2.
This was ALSO written by calling number 1.

In the above example, the recursion stopped when it reached four levels deep, but your function should be capable of continuing any specific level with the following function prototype.

     void indented_sentences(size_t m, size_t n);
// precondition: m <=n;
//postcondition: print out the above pattern by calling number from m to n