Fibonacci Using Recursion in DSA Typescript

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 numbers step by step.

Analogy: Imagine climbing stairs where each step depends on the sum of the two previous steps you took. To know how high you are on step n, you look back at steps n-1 and n-2 and add them.

fib(4)
  ↑
fib(3) + fib(2)
 ↑       ↑
fib(2)+fib(1) fib(1)+fib(0)
 ↑   ↑     ↑    ↑
1   1     1    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 the two previous Fibonacci numbers

Step 2: fib(3) calls fib(2) and fib(1)

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

Why: fib(3) breaks down further to find its two previous numbers

Step 3: fib(2) calls fib(1) and fib(0), both base cases return 1 and 0

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

Why: Base cases stop recursion and provide known values

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

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

Why: Calculate fib(3) and fib(2) values to sum for fib(4)

Step 5: Sum all: fib(4) = (1 + 1) + 1 = 3

fib(4) = 3

Why: Final addition gives the 4th Fibonacci number

Result:

fib(4) = 3

Annotated Code

DSA Typescript

class Fibonacci {
  static fib(n: number): number {
    if (n === 0) return 0; // base case: fib(0) = 0
    if (n === 1) return 1; // base case: fib(1) = 1
    return Fibonacci.fib(n - 1) + Fibonacci.fib(n - 2); // recursive call
  }
}

// Driver code
const n = 4;
console.log(`fib(${n}) = ${Fibonacci.fib(n)}`);

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

stop recursion when n is 0 and return 0

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

stop recursion when n is 1 and return 1

return Fibonacci.fib(n - 1) + Fibonacci.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 exponentially

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 more efficient than recursive

Edge Cases

n = 0

Returns 0 immediately as base case

DSA Typescript

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

n = 1

Returns 1 immediately as base case

DSA Typescript

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

n is negative

No guard in code; recursion will continue indefinitely (stack overflow)

DSA Typescript

No guard for negative input in code

When to Use This Pattern

When you see a problem asking for a sequence where each value depends on previous ones, try recursion to break it down into smaller subproblems.

Common Mistakes

Mistake: Missing 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 return causing undefined results
Fix: Return the sum of fib(n-1) and fib(n-2) properly

Summary

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

Use when you want a simple, clear way to find Fibonacci numbers and understand recursion.

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