Question

Hi. Please could you assist me with the question below. I found the same question on the Chegg website, unfortunately, the answer given does not make use of the driver function which is required by the question. Please could you provide me with the full code for this question, including the main function using c++ and codeblocks.

The standard recursive version of the Fibonacci function (explained in Malik pg. 379) is extremely inefficient due to identical calls being repeated. Consider the following iterative solution:
int fibonacci( int n )

{

if( n < 2 )

return n;

int oldprev = 0;

int prev = 1;

int result;

for( int i = 2; i <= n; i++ )

{

result = oldprev + prev;

oldprev = prev;

prev = result;

}

return result;

}

This function is far more efficient than the recursive version because it uses values previously computed.

Write a different recursive version of the Fibonacci function that is based on this idea (of the above iterative solution). It must be called from the following driver function:

int fibonacci( int n )

{

int oldprev;

return fibonacci( n, oldprev );

}

Thank You

Answer 1

SOURCE CODE:

*Please follow the comments to better understand the code.

**Please look at the Screenshot below and use this code to copy-paste.

***The code in the below screenshot is neatly indented for better understanding.

#include <iostream>
using namespace std;

// Helper function for fibonacci series
int helper_fibonacci(int oldprev, int prev, int steps_remaining)
{
//The Answer is here because steps_remaining=0
if(steps_remaining == 0)
return prev;
else if(steps_remaining == -1)
return oldprev;
else
//return the updated values as follows
return helper_fibonacci(prev, oldprev+prev, steps_remaining-1);
}

//fibonacci function here.
int fibonacci( int n )
{
int oldprev=1;
int prev = 1;
return helper_fibonacci(oldprev, prev, n-1 );
}

//Driver program to test the code.
int main()
{
cout<<"The First Ten Fibonacci Numbers are: "<<endl;
for(int i=1;i<=10;i++)
cout<<fibonacci(i)<<", ";
   return 0;
}

=======================

SCREENSHOTS: