Fibonacci Using Recursion in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Fibonacci Call

What is the output of the following C++ code snippet that calculates Fibonacci numbers recursively?

DSA C++

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int result = fib(5);
    std::cout << result << std::endl;
    return 0;
}

A 8

B 13

C 3

D 5

💡 Hint

Remember the Fibonacci sequence starts with 0, 1, 1, 2, 3, 5, 8...

fib(5) returns 5 (the 5th Fibonacci number, 0-indexed: 0,1,1,2,3,5). The output is 5.

❓ Predict Output

intermediate

Output of Recursive Fibonacci with Negative Input

What happens when the following recursive Fibonacci function is called with n = -1?

DSA C++

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int result = fib(-1);
    std::cout << result << std::endl;
    return 0;
}

A 1

B 0

C -1

D Stack overflow error

💡 Hint

Check the base case condition for n <= 1.

The base case returns n if n <= 1. Since -1 <= 1, fib(-1) returns -1 immediately without recursion.

🔧 Debug

advanced

Identify the Error in Fibonacci Recursive Function

What error will the following C++ code produce when compiled and run?

DSA C++

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 3);
}

int main() {
    std::cout << fib(4) << std::endl;
    return 0;
}

A Output: 5

B Runtime error due to stack overflow

C Output: 3

D Compilation error

💡 Hint

Check the recursive calls and base cases carefully.

The function calls fib(n - 3) but has no base case for n < 0, causing infinite recursion and stack overflow.

🧠 Conceptual

advanced

Time Complexity of Recursive Fibonacci

What is the time complexity of the naive recursive Fibonacci function defined as fib(n) = fib(n-1) + fib(n-2) with base cases fib(0)=0 and fib(1)=1?

A O(2^n)

B O(n)

C O(n^2)

D O(log n)

💡 Hint

Consider how many calls are made for each fib(n).

Each call to fib(n) makes two calls to fib(n-1) and fib(n-2), leading to exponential growth in calls, so time complexity is O(2^n).

🚀 Application

expert

Memoization to Optimize Recursive Fibonacci

Which of the following C++ code snippets correctly implements memoization to optimize the recursive Fibonacci function?

A

int fib(int n, std::vector<int>& memo) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 6;
    std::vector<int> memo(n + 1, -1);
    std::cout << fib(n, memo) << std::endl;
    return 0;
}

B

int fib(int n) {
    static std::vector<int> memo(100, -1);
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    std::cout << fib(6) << std::endl;
    return 0;
}

C

int fib(int n) {
    if (n <= 1) return n;
    int memo[100] = {-1};
    if (memo[n] != -1) return memo[n];
    memo[n] = fib(n - 1) + fib(n - 2);
    return memo[n];
}

int main() {
    std::cout << fib(6) << std::endl;
    return 0;
}

D

int fib(int n, int memo[]) {
    if (n <= 1) return n;
    if (memo[n] != 0) return memo[n];
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
    return memo[n];
}

int main() {
    int n = 6;
    int memo[7] = {0};
    std::cout << fib(n, memo) << std::endl;
    return 0;
}

💡 Hint

Memo array must be initialized outside recursion and passed correctly.

Option A correctly initializes a vector memo with -1, passes it by reference, and uses it to store computed values. Option A uses static vector but does not handle initialization properly for multiple calls. Option A initializes memo inside function each call, losing memoization. Option A uses 0 as default but 0 is a valid Fibonacci number, causing incorrect memo checks.

Practice

1. What does the Fibonacci sequence represent when calculated using recursion?

easy

A. Each number is the square of the previous number

B. Each number is the sum of the two preceding numbers starting from 0 and 1

C. Each number is the difference between the two preceding numbers

D. Each number is the product of the two preceding numbers

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence starts with 0 and 1, and each next number is the sum of the two before it.

2. Step 2: Relate to recursion

   Recursion calls the function for the two previous numbers and adds their results to get the current number.

3. Final Answer:

   Each number is the sum of the two preceding numbers starting from 0 and 1 -> Option B

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds last two numbers recursively [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or squares with Fibonacci
• Ignoring the base cases 0 and 1

2. Which of the following is the correct base case for a recursive Fibonacci function in C++?

easy

A. if (n == 1) return 0; if (n == 2) return 1;

B. if (n <= 2) return n;

C. if (n == 0) return 0; if (n == 1) return 1;

D. if (n == 0) return 1; if (n == 1) return 1;

Solution

1. Step 1: Identify correct Fibonacci base cases

   Fibonacci sequence starts with 0 at position 0 and 1 at position 1, so base cases must return these values.

2. Step 2: Match base cases to code

   if (n == 0) return 0; if (n == 1) return 1; correctly returns 0 for n=0 and 1 for n=1, matching Fibonacci definition.

3. Final Answer:

   if (n == 0) return 0; if (n == 1) return 1; -> Option C

4. Quick Check:

   Base cases match Fibonacci start [OK]

Hint: Base cases: 0 returns 0, 1 returns 1 [OK]

Common Mistakes:

• Using wrong base values like 1 for n=0
• Returning n for n <= 2 which is incorrect
• Confusing base cases with general recursive step

3. What is the output of the following C++ code?

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

int main() {
  std::cout << fib(5);
  return 0;
}

medium

A. 5

B. 8

C. 3

D. 13

Solution

1. Step 1: Calculate fib(5) using recursion

   fib(5) = fib(4) + fib(3). Calculate fib(4) = fib(3) + fib(2), fib(3) = fib(2) + fib(1), and so on until base cases.

2. Step 2: Evaluate values step-by-step

   fib(0)=0, fib(1)=1, fib(2)=1, fib(3)=2, fib(4)=3, fib(5)=5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   fib(5) = 5 [OK]

Hint: Remember fib(5) = 5 in Fibonacci sequence [OK]

Common Mistakes:

• Calculating fib(5) as 8 or 13 by mistake
• Confusing index starting point
• Skipping base cases in calculation

4. Identify the error in this recursive Fibonacci function:

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

medium

A. No error, function is correct

B. The recursive calls are in wrong order; should be fib(n-1) + fib(n-2)

C. Base cases are incorrect

D. Missing return type in function

Solution

1. Step 1: Check base cases

   Base cases for n==0 return 0 and n==1 return 1 are correct for Fibonacci.

2. Step 2: Check recursive step

   fib(n-2) + fib(n-1) equals fib(n-1) + fib(n-2) because addition is commutative. Function computes correct values. No error.

3. Final Answer:

   No error, function is correct -> Option A

4. Quick Check:

   Addition commutative, no error [OK]

Hint: Addition order irrelevant, commutative [OK]

Common Mistakes:

• Thinking recursive call order must be strictly n-1 first
• Assuming reversed order changes the result
• Overlooking commutativity of addition

5. How many times is the function fib called when computing fib(4) using the recursive function below?

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

hard

A. 5

B. 7

C. 15

D. 9

Solution

1. Step 1: Trace calls for fib(4)

   fib(4) calls fib(3) and fib(2). fib(3) calls fib(2) and fib(1). fib(2) calls fib(1) and fib(0).

2. Step 2: Count total calls

   Calls: fib(4), fib(3), fib(2), fib(1), fib(2), fib(1), fib(0), fib(1), fib(0) = 9 calls total.

3. Final Answer:

   9 -> Option D

4. Quick Check:

   Count recursive calls carefully = 9 [OK]

Hint: Count each fib call including duplicates [OK]

Common Mistakes:

• Counting only unique calls
• Ignoring repeated calls for same n
• Underestimating recursion tree size