CS1411 - Introduction to Programming Principles I

Programming / Lab Assignment 10

Warning: There will be points deducted if the assignmnent is not submitted in the correct format. Please see the submission guidelines!

Recursion

In this assignment you will solve a problem recursivly, iteratively and compare both versions.

The Assignmnent is from the book, pages 581/582, number 1, 6 and 7.

Since most modern computers are way too fast, you will get a result of 0 seconds on most of the timings you do. This will of course not help us. So instead of using the values provided in the book, please find values where your solutions take between 0.1 and 100 seconds

Add a results.txt file with your results in seconds, similar to this one (these values are pure fiction):

fib(x)     recursive   iterative   optimized recursive
1               0          0                 0
7               0.2        0                 0
100            10          0.5               0.43
1000         too long      1                 1.2
10000        too long      3                 stack overflow

Update: The numbers might get quite large before you can produce any reasonable results, you might run out of stack on the optmized recursive function. If so, it is sufficient if you write the larges number you sucessfully calulated, with 0 seconds, and then write "stack overflow" for the larger number

To do timeing, there are several different ways, most of them are not portable. So please choose a way that works with Visual Studio 6. The following way works on most plattforms (including Visual Studio and XCode):

...
#include <ctime>
...
{
  ...
  clock_t start,end;

  start = clock();
  ...
  end = clock();

  double time_passed = static_cast(end-start)/CLOCKS_PER_SEC;
  ...
}

A complete example is available here: timer.cpp. Thios example takes approx. 0.5 seconds on my computer.

When you do your timings, please make sure that you have as few other programs running as possible to get a good result.

Your programs should include comments whith you name, testnumber, etc. in the top. See also the Submission guidelines

The assignment is due Friday Nov 19, 6pm. You have to submit it electronically as stated in the submission guidelines!

Lost? See the Help! page.