Question

C++ Fibonacci

Complete ComputeFibonacci() to return FN, where F0 is 0, F1 is 1, F2 is 1, F3 is 2, F4 is 3, and continuing: FN is FN-1 + FN-2. Hint: Base cases are N == 0 and N == 1.
#include
using namespace std;
int ComputeFibonacci(int N) {
cout << "FIXME: Complete this function." << endl;
cout << "Currently just returns 0." << endl;
return 0;
}
int main() {
int N = 4; // F_N, starts at 0
cout << "F_" << N << " is "
<< ComputeFibonacci(N) << endl;
return 0;
}

Answer 1

int ComputeFibonacci(int N) {

if(N == 0)

return 0;

else if (N == 1)

return 1;

else

return ComputeFibonacci(N-1) + ComputeFibonacci(N-2);

}

Step-by-step explanation:

Inside the function ComputeFibonacci that takes one parameter, N, check the base cases first. If N is eqaul to 0, return 0. If N is eqaul to 1, return 1. Otherwise, call the ComputeFibonacci function with parameter N-1 and N-2 and sum these and return the result.

For example,

If N = 4 as in the main part:

ComputeFibonacci(4) → ComputeFibonacci(3) + ComputeFibonacci(2) = 2 + 1 = 3

ComputeFibonacci(3) → ComputeFibonacci(2) + ComputeFibonacci(1) = 1 + 1 = 2

ComputeFibonacci(2) → ComputeFibonacci(1) + ComputeFibonacci(0) = 1 + 0 = 1

*Note that you need to insert values from the bottom. Insert the values for ComputeFibonacci(1) and ComputeFibonacci(0) to find ComputeFibonacci(2) and repeat the process.