lab6.dvi

CS105 Lab 6 Due 12:30 10/24/97
This lab will give you a chance to work with the proof techniques we discussed in class before fall
break and once again compare recursion and loops. If you need to refer to the steps required to
prove something about a program, the list of steps in available on our web page - there is a link
to it from the description of \unit 5" in the web page that gives the syllabus for CMSC105, which
is http://www.haverford.edu/cmsc/course-pages/CMSC105page.html (the lists of steps were also
discussed in class and handed out).
1. Add an assertion giving the \loop invariant" to your loop-based fib3 function from lab 5.
You may refer to your recursive function rec
fib3 in this loop invariant, but do not use fib3
in your assertion (if you do, fib3 will become recursive as well, which may cause problems).
2. Use the techniques discussed in lecture to prove that your fib3 function produces the right
answer. You may do this either as an extensive comment in your program (put it near the
function), or on paper (which you should then hand in in class). You should show all five
steps of the proof, and identify each step.
3. Produce a recursive version of the fib3 function that performs the same number of additions
as your loop-based fib3, using the techniques for converting loops into recursion that we
discussed in lecture (this function should not use any loops). Include an extra parameter
that counts the number of additions performed in this function (this should not be a global
variable). Have your main program call both your loop-based function from Question 1 and
this new function, and print out the number of additions performed by each (you can leave
in place the global variable used to count the number of additions in the loop-based function,
as long as you use a parameter rather than a global variable in your new function).
4. The function swap, shown on the back of this page, is supposed to swap the values of x and
y (that is, change x so that it has the value that y had, and y so that it has the value that
x had). Answer the following two questions , either as comments at the end of your lab, or
on paper (you may use this page if you like, but if you do, put your name on it): (a) using
the techniques described in class, prove that this function does what it is supposed to do,
(b) describe what would change if we left out the \&" in the declarations of the parameters
of the function - would the function still do what it should?

void swap(int &x, int &y)
{
  int temp = x - y;
  x = y;
  y = temp;
  y = y + x;
}

main()
{
  int a, b;
  cout << ``enter a '';
  cin >> a;
  cout << ``enter b '';
  cin >> b;
  swap(a, b);
  cout << ``a is now '' << a << `` and b is now '' << b << endl;
}