Question

6. (20)The Fibonacci sequence is the series of integers 0, 1, 1,2, 3, 5, 8, 13, 21, 34, 55, 89.. 1 See the pattern? Each element in the series is the sum of the preceding two items. There is a recursive formula for calculating the nth number of the sequence (the oth number if Fib(0)-0): 8 Fib(N)-/N, if N 0 or 1 ifN> 1 Fib(N-2) Fib(N-1), a. b. c. Write a recursive version of the function Fibonacci. Write a nonrecursive version of the function Fibonacci Write a program to test the recursive and iterative versions of the function Fibonacci. (Test the N for different values, such as n=5, 10, 30, 40, 50)

in C++

Answer 1

#include <iostream>

using namespace std;

int Fib_Rec(int n) {
   if(n == 0) {
      return 0;
   } else if(n == 1) {
      return 1;
   } else {
      return Fib_Rec(n-1) + Fib_Rec(n-2);
   }
}

int Fib_Itr(int n) {
   int a0 = 0;
   int a1 = 1;
   if(n <= 1) {
      return n;
   } else {
      int an;
      for(int i = 2; i <= n; ++i) {
         an = a0+a1;
         a0 = a1;
         a1 = an;
      }
      return an;
   }
}

int main() {
   cout << "Enter n: ";
   int n;
   cin >> n;
   cout << "Fib(" << n << ") using recursion is: " << Fib_Rec(n) << endl;
   cout << "Fib(" << n << ") using non-recursion is: " << Fib_Itr(n) << endl;
   return 0;
}