Question

Homework 6 Problem 2 Translate the third of the following three algorithms to C++. Write a program to test the function. The first few Fibonacci numbers are 1,1,2,3,5,8,13,21,34,55,89,144,…

Fibonacci(n)

   f1 = 0

   f2 = 1

   fib = 0

   while n > 0

     f1 = f2

     f2 = fib

     fib = f1 + f2

     n = n – 1

   end while

   return fib

end fibonacci

fibonacci(n)

if n < 1 then

     return 0

else if n = 1 or 2 then

     return 1

else

     return fibonacci(n – 1) + fibonacci(n – 2)

end if

end fibonacci

fibonacci(n, f1, f2)

if n = ? then

     return f2

else

     return fibonacci(?, ?, ?)

end if

end fibonacci

Answer 1

fibonacci(n,f1,f2) is a recursive function where the base case will be

if n==2

return f2

and therecursive call will be

return fibonacci(n-1,f2,f1+f2)

here we have given n-1 in the function because it is a recursive function and thus the function will call on it's subparts.

the value of f2 becomes f1 as in above two codes and f2 becomes f1+f2.

CODE IN C++:

#include<iostream>
using namespace std;
int fibonacci(int n,int f1,int f2)
{

if(n ==2) { //here we have put n==2 because the base case is when n reaches 2 as we know that fib(1) and fib(2) ==1

return f2;
}

else{

return fibonacci(n-1, f2, f1+f2); //recursive call
}
}

int main()
{
int ans;
cout<<"Enter the number : ";
cin>>ans;
cout<<"Fibonacci of number is "<<ans;
}

OUTPUT SNIPPET: