250+ TOP MCQs on Fibonacci using Recursion and Answers

Data Structure Multiple Choice Questions & Answers (MCQs) on “Fibonacci using Recursion”.

1. Suppose the first fibonnaci number is 0 and the second is 1. What is the sixth fibonnaci number?
a) 5
b) 6
c) 7
d) 8

Answer: a
Clarification: The sixth fibonnaci number is 5.

2. Which of the following is not a fibonnaci number?
a) 8
b) 21
c) 55
d) 14

Answer: d
Clarification: 14 is not a fibonnaci number.

3. Which of the following option is wrong?
a) Fibonacci number can be calculated by using Dynamic programming
b) Fibonacci number can be calculated by using Recursion method
c) Fibonacci number can be calculated by using Iteration method
d) No method is defined to calculate Fibonacci number

Answer: d
Clarification: Fibonacci number can be calculated by using Dynamic Programming, Recursion method, Iteration Method.

4. Consider the following iterative implementation to find the nth fibonacci number?

int main()
{
    int  n = 10,i;
    if(n == 1)
        printf("0");
    else if(n == 2)
        printf("1");
    else
    {
        int a = 0, b = 1, c;
        for(i = 3; i <= n; i++)
        {
            c = a + b;
            ________;
			________;
        }
        printf("%d",c);
    }
   return 0;
}

Which of the following lines should be added to complete the above code?
a)

   c = b
   b = a

b)

   a = b
   b = c

c)

   b = c
   a = b

d)

   a = b
   b = a

Answer: b
Clarification: The lines “a = b” and “b = c” should be added to complete the above code.

5. Which of the following recurrence relations can be used to find the nth fibonacci number?
a) F(n) = F(n) + F(n – 1)
b) F(n) = F(n) + F(n + 1)
c) F(n) = F(n – 1)
d) F(n) = F(n – 1) + F(n – 2)

Answer: d
Clarification: The relation F(n) = F(n – 1) + F(n – 2) can be used to find the nth fibonacci number.

6. Consider the following recursive implementation to find the nth fibonacci number:

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return ________;
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

Which of the following lines should be inserted to complete the above code?
a) fibo(n – 1)
b) fibo(n – 1) + fibo(n – 2)
c) fibo(n) + fibo(n – 1)
d) fibo(n – 2) + fibo(n – 1)
Answer: b
Clarification: The line fibo(n – 1) + fibo(n – 2) should be inserted to complete the above code.

7. Consider the following recursive implementation to find the nth fibonnaci number:

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

Which of the following is the base case?
a) if(n == 1)
b) else if(n == 2)
c) return fibo(n – 1) + fibo(n – 2)
d) both if(n == 1) and else if(n == 2)

Answer: d
Clarification: Both if(n == 1) and else if(n == 2) are the base cases.

8. What is the time complexity of the following recursive implementation to find the nth fibonacci number?

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(2*n)
c) O(n²)
d) O(2ⁿ)
Answer: d
Clarification: The time complexity of the above recursive implementation to find the nth fibonacci number is O(2ⁿ).

9. What is the space complexity of the following recursive implementation to find the nth fibonacci number?

int fibo(int n)
{
     if(n == 1)
        return 0;
     else if(n == 2)
        return 1;
     return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) O(1)
b) O(2*n)
c) O(n²)
d) O(2ⁿ)

Answer: a
Clarification: The space complexity of the above recursive implementation to find the nth fibonacci number is O(1).

10. What is the output of the following code?

int fibo(int n)
{
      if(n == 1)
        return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = -1;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 0
b) 1
c) Compile time error
d) Runtime error

Answer: d
Clarification: Since negative numbers are not handled by the program, the function fibo() will be called infinite times and the program will produce a runtime error when the stack overflows.

11. What is the output of the following code?

int fibo(int n)
{
      if(n == 1)
        return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 5

Answer: c
Clarification: The program prints the 5th fibonacci number, which is 3.

12. How many times will the function fibo() be called when the following code is executed?

int fibo(int n)
{
      if(n == 1)
         return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 5;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 5
b) 6
c) 8
d) 9

Answer: d
Clarification: The function fibo() will be called 9 times, when the above code is executed.

13. What is the output of the following code?

int fibo(int n)
{ 
      if(n == 1)
        return 0;
      else if(n == 2)
        return 1;
      return fibo(n - 1) + fibo(n - 2);
}
int main()
{
     int n = 10;
     int ans = fibo(n);
     printf("%d",ans);
     return 0;
}

a) 21
b) 34
c) 55
d) 13

Answer: b
Clarification: The program prints the 10th fibonacci number, which is 34.

and Answers.