IC210 Lab 7

 

Functions and Recursion

Pre-lab homework. (RECOMMENDED – this week’s pre-lab is not required – but completing it is recommended, so that you can then make maximal use of the time in lab to get things done and get help as needed). Create two flowcharts/pseudocode, one for each of the following programs:

Your flowchart/pseudocode should focus on the conceptually difficult parts of the program’s control flow logic. 


Executive Summary: This lab consists of several independent problems. Some involve recursion and some do not. Show each solution to the instructor when you complete it.

1.     As this class progresses, we'll be doing some computing with "points", i.e. with x, y values. We'd like to read these from the user or from files in the usual ordered pair notation, i.e. (x, y). It sure would be nice to have a function readPoint that would do it for us. We should be able to use readPoint in the following ways:

 

Example Code Fragment

Input

Output

double x=0, y=0;
cout << "Enter point: ";
readPoint(cin,x,y);
cout << "x = " << x << ", ";
cout << "y = " << y << endl;

(3.5,-0.1) from user

x = 3.5, y = -0.1

double x=0, y=0;
ifstream fin("data.txt");
readPoint(fin,x,y);
cout << "x = " << x << ", ";
cout << "y = " << y << endl;

(0.5,-4.4) from data.txt

x = 0.5, y = -4.4

Notice how readPoint modifies the two double values passed to it!

Define the function readPoint and write a main() that will test it for both file and console output.

Sample output

 

Problem 2: Write a recursive function writeReverse(istream& in, ostream& out) that reads in strings from the input stream IN (i.e. either typed by the user or from a file) terminated with the word "end" and prints the strings to the stream OUT out in reverse order. For example, if the call from main() looks like writeReverse(cin, cout) and the user types

2.  I am sam end

then writeReverse should print out

sam am I
 
You should NOT use an array.  You also do NOT need a loop – use recursion instead!
 
Sample output

Problem 3: An arithmetic sequence is a sequence of the form:

a, a + b, a + 2b, a + 3b, ...

Write a program that reads integers a and b from the user along with positive integer n, and prints out the first n terms of the arithmetic sequence defined by a and b. The trick is you may not use loops! Thus, you need to use recursion. Hint: The sequence can also be written as a + b(i-1) for i = 1 to n. Think of what the base case is, and what the recursive case is of this sequence. Here is a sample run:

Sample output

 

 
GOING BEYOND

If you finish the above during lab time, try to solve the following:

Beyond #1: Suppose we want programs that are able to output time in hh:mm:ss format. Our programs will probably calculate things in seconds, but the user would prefer to see something like 02:00:23 (i.e. 2 hours, 0 minutes and 23 seconds) instead of 7223 seconds.

Define a function writeTime that prints out a given number of seconds in the proper format to either the screen or a file.  Write a main()to test your function.  It should read in a number of seconds from the user and either the word "screen" or a file name, and prints the time in hh:mm:ss format to either the console or a file with the given name.  writeTime should only take two arguments, an ostream object and an int.  We should be able to use writeTime in the following ways: 

Example Code Fragment

Writes

int s = 7223;
writeTime(s, cout);

02:00:23 to the screen.

int s = 7223;
ofstream fout("test.txt);
writeTime(s, fout);

02:00:23 to test.txt

 

Sample run for output to the screen

 

Sample run for output to the file...time.txt

 

Beyond #2: Challenge Problem
Write a program that reads a positive integer n from the user and prints out all n-digit binary numbers, one per line.

Hint 1: write a function with prototype listbins(string front, int n); which, assuming that n is not negative, will print out all the different strings you can get by tacking an n-bit binary number onto the back of the string front. So, for example, listbins("hello",2) should produce the following output:

hello00
hello01
hello10
hello11
 

If you get listbins working you're done, since listbins("",n) prints out all n-bit binary numbers. This illustrates an important technique. Your first thought is probably "I'd like a function listbins(int n); that prints out all n-bit binary numbers." However, we need to throw in an extra argument which, from the perspective of a "user" of the function is unnecessary, but which from the implementer's perspective we need so we can pass partial results along to the next recursive call. In essence, the more general, flexible and powerful function listbins(front,n) is easier to write than the more specific function listbins(n).

Hint 2: Remember that + concatenates strings or strings and characters. So if s = "do" and t = "ne" then s + t is the string "done", and s + 't' is the string "dot".