a c++ question Part 1 Write a recursive function definition for a function that

Question

a 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.

Notes

// main.cpp

#include <iostream>
#include <chrono>    // 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 << " Elapsed time: "
        << duration_cast<nanoseconds>(t1 - t0).count()
        << " nanoseconds ";

    return 0;
}

Explanation / Answer

#include <iostream>

int fibonacci(int n)
{
return ( n<=2 ? 1 : fibonacci(n-1) + fibonacci(n-2) );
}

int main(void)
{
for (int n=1; n<=16; n++)
std::cout << fibonacci(n) << ", ";
std::cout << "..." << std::endl;
return 0;
}

3)

Roughly speaking, recursion and iteration perform the
same kinds of tasks: ! Solve a complicated task one piece at a time, and
combine the results. Emphasis of iteration: ! keep repeating until a task is

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.