[Solved] CS-Module 4

Compare iterative and recursive implementations of a common algorithm

You will be working with recursive and iterative implementation of Fibonacci Number algorithms. You will be measure the running time of each and compare them.

You do not need to implement the algorithms! Feel free to find the source online, or in a book. Just ensure you cite the source! Here is one site that discusses both versions:

http://www.codeproject.com/Tips/109443/Fibonacci-Recursive-and-Non-Recursive-C

I am not endorsing this site; it is simply the first I found that integrates both.

You must modify the program to measure the running time. You can use this reference to measure execution time: http://www.cplusplus.com/reference/ctime/clock/. You can use any other timing mechanism you chose (other than wall clock time). Your TA(s) may suggest another method (many have their own favorite). As discussed in class, the difference should be visible quickly so you wont need very precise measurements.

Before you start write down your expectations.

Then compile and run your program(s). Record your measurements present then with your analysis.

HINT: Start with small values of N.

So far youve done double recursion and iteration. At the bottom of this document there is sample code for recursive factorial and tail-recursive factorial functions. Add these functions to your program or write a new program (classes are not required). Insert the timing code and compile and run your program. To take advantage of the tail recursion youll need to turn some level of optimization on. Use the man pages on flip or do online research to find out what you need. Compare the results of iteration, tail-recursion, single recursion, and double recursion. Are they what you expected?

HINT: Start with small values of N.

NOTE: An important skill in software development is doing research for ideas or known solutions to problems. In this case the simple searches were done for you. But get in the habit of including citations in the comments for each file! The CodeProject site is a good example of licensing. It is clear that others can use this code as long as they do not claim it as their own. An important point when borrowing code!