Why Memoization to Optimize Recursion in DSA Typescript?

The Big Idea

What if your program could remember answers and never repeat the same work twice?

The Scenario

Imagine you are solving a puzzle where you need to find the number of ways to climb stairs, but you keep recalculating the same steps over and over again.

This wastes time and makes you frustrated.

The Problem

Doing the same calculations repeatedly is slow and tiring.

It's like writing the same answer again and again by hand instead of remembering it.

This makes your program slow and uses more energy.

The Solution

Memoization helps by remembering answers to small problems once you solve them.

Next time you need the same answer, you just look it up instead of solving again.

This saves time and makes your program faster and smarter.

Before vs After

✗ Before

function fib(n: number): number {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

✓ After

function fib(n: number, memo: Record<number, number> = {}): number {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

What It Enables

Memoization makes slow recursive problems run fast enough to solve big puzzles easily.

Real Life Example

Calculating Fibonacci numbers quickly to generate beautiful patterns or solve math problems without waiting forever.

Key Takeaways

Manual recursion repeats work and wastes time.

Memoization stores results to avoid repeated work.

This makes recursive solutions efficient and practical.