C++ question Part 1
Write a recursive function definition for a function that has one parameter N of type int and that returns the Nth Fibonacci number. The Fibonacci numbers are F0 is 1, F1 is 1, F2 is 2, F3 is 3, F4 is 5, and in general
Fi+2 = Fi + Fi+1 for i = 2, 3, 4, ...
Your client code should prompt the user for N, call the function to compute and return the Nth Fibonacci number, and output the result.
Part 2
You need to have first completed Part 1 to work on this part.
When computing a Fibonacci number using the most straightforward recursive function definition, the recursive solution recomputes each Fibonacci number too many times. To compute Fi + 2 = Fi + Fi + 1, it computes all the numbers computed in F i a second time in computing Fi + 1. You can avoid this by saving the numbers in an array while computing Fi.
Write another version of your recursive Fibonacci function based on this idea. In this recursive solution for calculating the Nth Fibonacci number, create a dynamic array of size N+1, with the array elements at indices 0 and 1 initialized to 1, and the rest of the array elements (2, 3, ... N) initialized to some invalid value (e. g., a named constant NO_VALUE assigned to -1). When the ith Fibonacci number is computed the first time, store it in the array entry i. Then use the array to avoid any further (redundant) recalculation of the Fibonacci numbers.
For this part, your client code should prompt the user for N, create the dynamic array of size N+1, call the function with the array to compute and return the Nth Fibonacci number, and output the result.
part 3
You need to have first completed Part 1 to work on this part.
In this exercise, you will compare the efficiency of a recursive and an iterative function to compute the Fibonacci number.
Examine the recursive function computation of Fibonacci numbers. Note that each Fibonacci number is recomputed many times. To avoid this recomputation, redo Part 1 iteratively, rather than recursively; that is, do the problem with a loop. You should compute each Fibonacci number once on the way to the number requested and discard the numbers when they are no longer needed.
Time1 the solution for Part 1 and Part 3a in finding the 1st, 3rd, 5th, 7th, 9th, 11th, 13th, and 15th Fibonacci numbers. Determine how long each function takes. Compare and comment on your results.
Notes
To time execution of (part of) a C++ 11 program, you can use the chrono library, and the std::chrono nested namespace, as follows:
// main. cpp
#include
#include // for timing
int main()
{
using namespace std;
using namespace std::chrono;
// some program code
auto t0 = high_resolution_clock::now();
// code to be timed
auto t1 = high_resolution_clock::now();
cout << "\nElapsed time: "
<< duration_cast(t1 - t0).count()
<< " nanoseconds\n";
return 0;
}