More Recursion in C

Due 11:55pm on Wednesday, February 19, 2020.

Exercise 1

Write a program that repeatedly reads an integer, and determines if it is a triangular number. A triangular number T_n is defined as 1+2+3+...+n. For more on triangular numbers, see this Wikipedia article.

• Prompts the user to enter a number with "Number ?\n"
• Assume the user will only enter a positive number small enough to fit within an int, or enter 0 to stop the program. The number entered will always be in decimal format, so '010' should be interpreted as ten not eight.
• If the number entered is a triangular number, the program prints "num is a triangular number", else prints "num is not a triangular number", followed by a newline.
• The program repeats, prompting for the next input, until the user enters a 0, in which case the program prints "Done", followed by a newline, and terminates.

You can choose to implement the calculation of triangular numbers either as the sum 1+2+3+...+n, or using a formula, or a recursive definition.

Here is one execution scenario:

Number ?

1

1 is a triangular number

Number ?

2

2 is not a triangular number

Number ?

3

3 is a triangular number

Number ?

20

20 is not a triangular number

Number ?

21

21 is a triangular number

Number ?

0

Done

First test your program by running it through the execution scenario above, and make sure it produces exactly the same output. Name the file with the C program ex1.c. Compile it to ex1 and test it on the sample input and output file provided (ex1in1).

Exercise 2: Binary Pattern Generation

In this exercise, you will write a recursive function that, given a number N, generates all binary patterns of length N. For example, for N=3, it will output:

000
001
010
011
100
101
110
111

Likewise, if N were 4, the output will be 16 lines long, corresponding to the binary strings of length 4, in increasing order, starting with 0000 and ending with 1111.

This exercise must be done using recursion. Remember that recursion is very different from iteration (for/while loops). You must create a procedure that calls itself. In particular, to generate all binary patterns of length N, do the following. First, set the leftmost position to '0', and generate all binary patterns over the remaining N-1 positions. Next, set the leftmost position to '1', and again generate all binary patterns over the remaining N-1 positions.

Assume N will not be more than 10. Name your file ex2.c, and test using your own inputs as well as the input/output sample files.

A code skeleton for this exercise is available. However, to derive the most benefit from this exercise, please spend a few minutes writing your own C code first (or at least pseudocode / algorithm), before looking at the skeleton.

Exercise 3: More Patterns

Modify your program from Exercise 2 so that only those patterns are generated that do not contain two (or more) consecutive '1's. Thus, for N=3, the output will now be:

000
001
010
100
101

This problem can be approached two ways. One way is to prevent a recursive call for a '1' in a certain position if its prior position (to the left) also had a '1'. This is the prefered approach. (It is possible to do this by changing/inserting a single line of C code into the code from the previous exercise.) A second approach is to generate all patterns, but skip printing a pattern if it contains consecutive '1's. This will require a bit more work.

Name your file ex3.c, and test using your own inputs as well as the input/output sample files.

Test Inputs, Due Date and Submission Procedure

Your assignment must be submitted electronically via Sakai by 11:55pm on Wednesday, February 19, 2020. You will submit your work on Exercises 1-3, specifically, the files ex1.c, ex2.c and ex3.c.

Sample Inputs/Outputs: Sample inputs and corresponding outputs are provided under /home/montek/comp411/samples/lab6. The sequence of steps to run your program and verify its output is as follows. First, copy all the sample input and output files to your lab6 folder:

% cd ~/comp411lab/lab6
% cp /home/montek/comp411/samples/lab6/* .
% selfchecklab6

How to submit: First transfer your work back to your laptop by either using WinSCP (for Windows), or Cyberduck/FileZilla/Macfusion or terminal/shell (for Mac/Linux), as explained in Lab 1. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.

Resubmissions: You are allowed to submit a lab assignment as many times as you would like to, but only the latest submission will be considered for grading.

In case of any problems, please contact the instructor or the TAs.