Fibonacci Using Recursion in DSA C++

Mental Model

Calculate each Fibonacci number by adding the two before it, using a function that calls itself.

Analogy: Like climbing stairs where to reach step n, you first need to know how to reach step n-1 and n-2, and you keep asking yourself how to get there until you reach the base steps.

fib(4)
  /    \
fib(3)  fib(2)
 /  \     /  \
fib(2) fib(1) fib(1) fib(0)
 /  \
fib(1) fib(0)

Dry Run Walkthrough

Input: Calculate fib(4)

Goal: Find the 4th Fibonacci number using recursion

Step 1: Call fib(4), which calls fib(3) and fib(2)

fib(4) -> fib(3) + fib(2)

Why: To find fib(4), we need fib(3) and fib(2)

Step 2: Call fib(3), which calls fib(2) and fib(1)

fib(3) -> fib(2) + fib(1)

Why: To find fib(3), we need fib(2) and fib(1)

Step 3: Call fib(2), which calls fib(1) and fib(0)

fib(2) -> fib(1) + fib(0)

Why: To find fib(2), we need fib(1) and fib(0)

Step 4: fib(1) returns 1 and fib(0) returns 0, so fib(2) = 1 + 0 = 1

fib(2) = 1

Why: Base cases return fixed values

Step 5: fib(1) returns 1, so fib(3) = fib(2) + fib(1) = 1 + 1 = 2

fib(3) = 2

Why: Combine results to get fib(3)

Step 6: Call fib(2) again, which returns 1 as before

fib(2) = 1

Why: fib(2) is calculated again recursively

Step 7: fib(4) = fib(3) + fib(2) = 2 + 1 = 3

fib(4) = 3

Why: Final result combines previous two Fibonacci numbers

Result:

fib(4) = 3

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Recursive function to find Fibonacci number
int fib(int n) {
    if (n == 0) return 0; // base case 0
    if (n == 1) return 1; // base case 1
    return fib(n - 1) + fib(n - 2); // recursive call
}

int main() {
    int n = 4;
    cout << "fib(" << n << ") = " << fib(n) << endl;
    return 0;
}

if (n == 0) return 0; // base case 0

return 0 when n is 0 to stop recursion

if (n == 1) return 1; // base case 1

return 1 when n is 1 to stop recursion

return fib(n - 1) + fib(n - 2); // recursive call

calculate fib(n) by adding fib(n-1) and fib(n-2)

Output

fib(4) = 3

Complexity Analysis

Time: O(2^n) because each call splits into two more calls, doubling work exponentially

Space: O(n) due to the maximum depth of the recursion call stack being n

vs Alternative: Compared to iterative approach which is O(n) time, recursion is slower and repeats calculations

Edge Cases

n = 0

Returns 0 immediately as base case

DSA C++

if (n == 0) return 0; // base case 0

n = 1

Returns 1 immediately as base case

DSA C++

if (n == 1) return 1; // base case 1

negative n

No guard, function will recurse infinitely (undefined behavior)

DSA C++

No explicit guard for negative input

When to Use This Pattern

When a problem asks for a sequence where each value depends on previous two, use recursion to break it down into smaller subproblems.

Common Mistakes

Mistake: Forgetting base cases causes infinite recursion
Fix: Add base cases for n == 0 and n == 1 to stop recursion

Mistake: Calling fib(n-1) + fib(n-2) without return causes no result
Fix: Use return statement to combine recursive calls and return the sum

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs.

Use when you want a simple, clear way to find Fibonacci numbers but input size is small.

The key is to stop recursion at base cases and combine smaller results to build the answer.

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