lab5.dvi

CS105 Lab 5 Due 12:30 10/10/97
This lab will give you a chance to compare recursion and loops again, using some variations on the
Fibonacci sequence (which is discussed on pages 509-514 of the textbook (don't panic - we haven't
covered the first 500 pages already - I'm just picking an example from Chapter 10 that doesn't rely on
anything from Chapters 6-9)). In this variation of the Fibonacci sequence, the first three numbers are all
1, and the other numbers are defined as the sum of the previous three elements of the sequence. Thus,
the sequence starts out 1 1 1 3 5 9 17 31 ... We'll call this sequence Fib3, and write several functions to
find the numbers in this sequence.
You should put the functions for Questions 1 and 2 in a separate file, called fib3.c (you'll have to use
\add file" to add this to the list of source files for your program). You should include a main function,
in main.c, that asks the user for input and shows the results of the functions you are writing. All of the
input and output should be done from functions in main.c. You'll also need a file named fib3.h which
includes the declarations of your functions (and global variables, when you get to question 3), and is
#include-d in fib3.c and main.c.
Questions 4 and 5 are short answer questions, rather than programming questions. give your answers
to them in comments at the end of your main.c file.
1. Create a recursive function int rec
fib3(int i) that computes element i of the above variation
of the Fibonacci sequence. Your function, like the one in the book, should treat i=0 as a request for
the initial element of the sequence. That is, rec
fib3(0), rec
fib3(1), and rec
fib3(2) should produce
1, rec
fib3(3) should produce 3, and rec
fib(4) should produce 5. Do not use any loops in your
answer to this question.
2. Create a function int fib3(int i) that uses a loop to compute the same result as rec
fib3(i).
3. Create global variables rec
fib3
adds and fib3
adds to count the number of times addition is
performed in rec
fib3 and fib3. You'll need to increment these variables each time you do an
addition in the associated function, and have your main function reset them to zero before calling
your functions. Your main function should include a loop to let the user enter different values for
i, and show rec
fib3(i), fib3(i), and the number of additions performed by each. The number of
additions reported should be the total for the given value of i - if the user first enters 5 (to get
fib3(5)), and then 3 (to get fib
3(3)), the number of additions printed for fib3(3) should not include
the additions needed for fib3(5).
4. Consider the following sequence, which we'll call fibi, which starts with 1, and then each number
is the sum of all previous numbers in the sequence. So fibi(0)=1, and fibi(1) = fibi(0) (which is 1),
and fibi(2) = fibi(1)+fibi(0)=2, etc. We could try to write recursive or loop-based functions like
those above to compute fibi, but there is a more efficient way to do so - what is it? (Hint - write
down the first few elements of the sequence). Give your answer as a comment at the end of main.c.
5. Suppose we wanted a program to print out the first n elements of the Fibonacci or fib3 sequence.
The function below shows one way to do this, but it does a lot of redundant work. Describe (in a
sentence or two) what this redundant work is, and describe a way to avoid this work. Could this
work could be avoided in a program that separates computation and i/o in different files? If so,
explain how; if not, explain why not. Give your answer to this question as a comment after your
answer to Question 4.
void print
the
first
n
fib3
numbers(int n)
f
int i;
for (i = 0; i < n; i++)
cout << ``fib3('' << i << ``) is '' << fib3(i) << endl;
g