Fibonacci Using Recursion in DSA C

Mental Model

Fibonacci numbers are found by adding the two numbers before it, starting from 0 and 1. Recursion means the function calls itself to find these previous numbers.

Analogy: Imagine climbing stairs where each step depends on the sum of the two steps before it. To know step 5, you ask about step 4 and step 3, and to know those, you ask about their previous steps, until you reach the first two steps which are known.

fib(n)
  ↓
fib(n-1) + fib(n-2)
  ↓         ↓
fib(n-2)+fib(n-3) + fib(n-3)+fib(n-4)
  ...
Base cases: fib(0)=0, fib(1)=1

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: fib(4) depends on fib(3) and fib(2) by definition

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

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

Why: fib(3) breaks down into fib(2) and fib(1)

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

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

Why: fib(2) breaks down into fib(1) and fib(0)

Step 4: fib(1) returns 1 and fib(0) returns 0

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

Why: Base cases reached, return known values

Step 5: Calculate fib(2) again as fib(1) + fib(0) = 1 + 0 = 1

fib(4) -> (1 + 1) + 1

Why: fib(2) is 1, used twice in calculation

Step 6: Sum all parts: fib(4) = 2 + 1 = 3

fib(4) = 3

Why: Final sum gives the 4th Fibonacci number

Result:

fib(4) = 3

Annotated Code

DSA C

#include <stdio.h>

// 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;
    int result = fib(n);
    printf("fib(%d) = %d\n", n, result);
    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

call fib for previous two numbers and add results

Output

fib(4) = 3

Complexity Analysis

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

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

vs Alternative: Iterative approach is O(n) time and O(1) space, much faster and uses less memory

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 guard for negative input in code

When to Use This Pattern

When you see a problem asking for a sequence where each term depends on previous terms, think of recursion to break it down into smaller subproblems.

Common Mistakes

Mistake: Not defining base cases causing infinite recursion
Fix: Add base cases for n=0 and n=1 to stop recursion

Mistake: Calling fib(n-1) and fib(n-2) without returning their sum
Fix: Return the sum of fib(n-1) and fib(n-2) to get correct result

Summary

Calculates Fibonacci numbers by calling itself with smaller inputs until base cases.

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

The key is breaking the problem into two smaller Fibonacci calls and combining their results.

Practice

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

easy

A. Each number is the sum of the two preceding numbers

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

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

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

Solution

1. Step 1: Understand Fibonacci sequence definition

   The Fibonacci sequence is defined such that each number is the sum of the two numbers 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 -> Option A

4. Quick Check:

   Fibonacci = sum of two previous numbers [OK]

Hint: Fibonacci adds previous two numbers recursively [OK]

Common Mistakes:

• Thinking Fibonacci multiplies previous numbers
• Confusing subtraction or division with addition
• Assuming Fibonacci uses only one previous number

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

easy

A. if (n < 2) return 2;

B. if (n == 0) return 0; else return 1;

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

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

Solution

1. Step 1: Identify base cases for Fibonacci

   Fibonacci sequence starts with 0 and 1 for n=0 and n=1 respectively, so base case returns n when n is 0 or 1.

2. Step 2: Match base case syntax

   The condition if (n <= 1) return n; correctly returns 0 for n=0 and 1 for n=1.

3. Final Answer:

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

4. Quick Check:

   Base case returns n for n=0 or 1 [OK]

Hint: Base case returns n when n is 0 or 1 [OK]

Common Mistakes:

• Returning 2 for base case
• Returning 0 for n=1 incorrectly
• Missing base case leading to infinite recursion

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

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

int main() {
  printf("%d", fib(4));
  return 0;
}

medium

A. 4

B. 3

C. 5

D. 7

Solution

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

   fib(4) = fib(3) + fib(2) - fib(3) = fib(2) + fib(1) = (fib(1)+fib(0)) + 1 = (1+0)+1=2 - fib(2) = fib(1) + fib(0) = 1 + 0 = 1 So fib(4) = 2 + 1 = 3

2. Step 2: Confirm output printed

   The printf prints the integer 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   fib(4) = 3 [OK]

Hint: Trace fib calls down to base cases [OK]

Common Mistakes:

• Confusing fib(4) with fib(5)
• Adding wrong fib values
• Forgetting base cases

4. Identify the error in this recursive Fibonacci function and select the fix:

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

medium

A. Add base case for n == 1 to return 1

B. Change return 0 to return 1 for n == 0

C. Remove else and just return fib(n-1) + fib(n-2)

D. Change function to iterative instead of recursive

Solution

1. Step 1: Check base cases

   Function only returns 0 for n==0 but misses base case for n==1, causing infinite recursion for n=1.

2. Step 2: Fix by adding base case for n==1

   Adding if (n == 1) return 1; fixes recursion and returns correct Fibonacci values.

3. Final Answer:

   Add base case for n == 1 to return 1 -> Option A

4. Quick Check:

   Both n=0 and n=1 base cases needed [OK]

Hint: Always include base cases for n=0 and n=1 [OK]

Common Mistakes:

• Missing base case for n=1
• Changing base case values incorrectly
• Removing else causing syntax confusion

5. You want to compute the 6th Fibonacci number using recursion but want to avoid repeated calculations. Which approach improves efficiency?

hard

A. Call fib(n-1) twice to ensure correctness

B. Increase the recursion depth limit

C. Use a loop instead of recursion without storing values

D. Use memoization to store and reuse computed Fibonacci values

Solution

1. Step 1: Understand repeated calculations in recursion

   Recursive Fibonacci calls fib(n-1) and fib(n-2) repeatedly, causing many duplicate calls and inefficiency.

2. Step 2: Use memoization to store results

   Memoization saves computed Fibonacci values in a cache, so repeated calls return stored results instantly, improving speed.

3. Final Answer:

   Use memoization to store and reuse computed Fibonacci values -> Option D

4. Quick Check:

   Memoization avoids repeated work [OK]

Hint: Store results to avoid repeated recursive calls [OK]

Common Mistakes:

• Increasing recursion depth doesn't fix inefficiency
• Using loops without caching still repeats work
• Calling fib(n-1) twice wastes time