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.