Recursive Fibonacci In class we saw the following very natur

Recursive Fibonacci
In class we saw the following very natural recursive code for computing Fibonacci numbers:
#include<iostream.h>
int fib(int n){
if(n==1 || n==2) return 1;
return fib(n-1)+fib(n-2);
};
void main(){
for(int i=1; i<70; i++)
cout<<\" fib(\"<<i<<\") = \"<<fib(i)<<endl;
}

Questions:
1. Why does the program get increasingly slower for each successive value of i?
2. What technique can we use to speed it up? Write the code.
3. After some value if i, the values printed for fib(i) get quite “strange.”
a. What is strange about them and why is this happening?
b. How can we fix this up?

Solution

#include <iostream>

using namespace std;

int fib(int n){
if(n==1 || n==2) return 1;
return fib(n-1)+fib(n-2);
};
int main(){
for(int i=1; i<70; i++)
cout<<\" fib(\"<<i<<\") = \"<<fib(i)<<endl;
return 0;
  
}

Questions:

1. Why does the program get increasingly slower for each successive value of i?
Ans: program getting slower for each successive value of i as recursive function is used.
In recursive function the calculated subparts are called repeatedly which results into slowerness of the program.
     

2. What technique can we use to speed it up? Write the code.  
Ans: We can use the dynamic programming approach here as we can remember the already calculated subparts and use them to calculate the further parts.
For example:fib(3)=1,1,2 :logic=each term is the calculation of previous two terms so we could store the values calculated previously and use them to calculate
   further terms.
     
//code :Using dp approach,has been tested faster than previous code having recursive approach
#include <iostream>

using namespace std;

int fibarr[70]; //global array for storing calculated fibnocci values   
int fib(int n){
if(n==1 || n==2) //if n==1 or n==2,store 1 at index 1 and 2 of array:fibarr
fibarr[n]=1;
else
fibarr[n]=fibarr[n-1]+fibarr[n-2]; //use the stored value from fibarr to calculate the new terms
return fibarr[n]; //return value
};
int main(){
  
for(int i=1; i<70; i++)
cout<<\" fib(\"<<i<<\") = \"<<fib(i)<<endl;
return 0;
  
} //end of code

3. After some value if i, the values printed for fib(i) get quite “strange.”
Ans:getting negative values is strange,for example:fib(69) = -188547518

a. What is strange about them and why is this happening?  
Ans:The negative values are strange,this is happening as we had used integer and we are calculating fib upto 70 values so due to large result,it is
crossing the range of integer and giving the strange values.

b. How can we fix this up?  
Ans: We must use long int instead of int.
//Code:
#include <iostream>

using namespace std;

long int fibarr[70]; //long int has been used
long int fib(int n){ //long int has been used
if(n==1 || n==2)
fibarr[n]=1;
else
fibarr[n]=fibarr[n-1]+fibarr[n-2];
return fibarr[n];
};
int main(){
  
for(int i=1; i<70; i++)
cout<<\" fib(\"<<i<<\") = \"<<fib(i)<<endl;
return 0;
  
}
//end of code.