Recursion

This lab has two parts:

Part I:

Write a short C++ program that contains two fibonacci functions. One is the recursive one that we coded in class; the other is an iterative version. Both functions take one integers parameter x, and return the x^th Fibonacci number in the sequence (given that the first two in the sequence are 1 and 1) . If you need help with the iterative version, see Chapter 5 in your book!

Your main function should prompt the user for a number and call each of the fib functions to get a result. Of course, both functions should return the same result!

Your main code might be:

long recurseResult,iterResult;

int z;

cin >> z;

recurseResult = fibRecurs(z);

iterResult = fib(z);

cout << endl << "Recursive result: "<< recurseResult << "\nIterative result: " << iterResult;

If your program includes the windows.h header file, your program can call the function GetTickCount()

GetTickCount() returns a long integer that holds the number of milliseconds since the device booted. (You can check out: http://msdn.microsoft.com/en-us/library/ms885645.aspx for more details, if you like)

Suppose the following code:

DWORD q; //DWORD is an unsigned long integer

q = GetTickCount();

//call the function that you wish to time here

q = GetTickCount()-q; //subtracts old milliseconds from new

cout << endl << "q:" << q << endl;

q will hold the number of milliseconds that the timed function took to execute!

Add the timing to your code, so that you time the iterative function and the recursive function. Remember that these are milliseconds so any call that takes less than one millisecond will be zero. How many milliseconds does the iterative function, and recursive function take if the parameter is: 10? 20? 30? 40?

Part II

Use a recursive function to reverse a list. Assume a list of integers. Hint: The recursive function takes an array, and a starting index and ending index.