Recursion and Dynamic Programming

From structures to strategies

Now that we have covered Arrays and Linked Lists, Stacks and Queues, Trees, Graphs, Hash Tables, and Sorting and Searching Algorithms, you have seen many ways to organize data.

This lesson shifts focus to a problem-solving strategy: recursion and its optimization partner, dynamic programming.

You have already used the underlying ideas:

• Tree traversals naturally visit smaller subtrees.
• Graph DFS explores neighbors recursively or with a stack.
• Binary search repeatedly solves a smaller search range.

Today we will make that pattern explicit: solve a big problem by solving smaller versions of the same problem, then avoid repeating work.

The two-part contract

A recursive function calls itself, but good recursion is not just self-calling. It needs two pieces:

1. Base case: the simplest input that can be answered immediately.
2. Recursive case: reduce the problem toward the base case.

A helpful question:

If I already knew the answer for a smaller input, how would I build the answer for this input?

For example, factorial follows this shape:

• factorial(1) = 1
• factorial(n) = n * factorial(n - 1)

Each call moves closer to the base case.

```javascript
function factorial(n) {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case
}

console.log(factorial(1)); // 1
console.log(factorial(5)); // 120
```

Recursion uses a stack

In Stacks and Queues, we learned that a stack is last-in, first-out. Recursive calls use the program's call stack in the same way.

When a function calls itself:

• the current call pauses,
• a new call is pushed onto the call stack,
• once the base case returns, calls pop off one by one.

That means recursion has two costs:

• Time: how many calls happen?
• Space: how deep does the call stack get?

For factorial(5), there are 5 calls and stack depth is 5, so both are O(n).

A recursive function is meant to process an array from index i to the end.

Which base case most directly means there are no elements left to process?

Where recursion gets expensive

Some recursive solutions branch into multiple calls. That can be fine, but it can also repeat the same work many times.

The classic example is Fibonacci:

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n - 1) + fib(n - 2)

A direct recursive version recomputes values like fib(3) and fib(4) again and again.

This is the bridge to dynamic programming:

If the same subproblem appears repeatedly, store its answer and reuse it.

Top-down dynamic programming

Memoization keeps the recursive style but adds a cache.

Before solving a subproblem, ask:

• Have I already computed this input?
• If yes, return the saved value.
• If no, compute it once and store it.

In JavaScript, a Map is a clean fit. That connects directly to the Hash Tables lesson: use key-value lookup to avoid repeated work.

```javascript
function fib(n, memo = new Map()) {
  if (n <= 1) return n;

  if (memo.has(n)) {
    return memo.get(n);
  }

  const result = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fib(10)); // 55
console.log(fib(40)); // 102334155
```

True or false?

Memoization can turn some recursive solutions from exponential time into polynomial or linear time by avoiding repeated subproblems.

Bottom-up dynamic programming

Memoization starts with the big problem and recursively asks for smaller ones.

Tabulation goes the other direction:

1. Start from known base cases.
2. Fill a table from small answers to larger answers.
3. Return the final entry.

Example: number of ways to climb n stairs when you can take 1 or 2 steps.

To reach stair i, you came from:

• i - 1, using a 1-step move
• i - 2, using a 2-step move

So ways[i] = ways[i - 1] + ways[i - 2].

```javascript
function climbStairs(n) {
  if (n <= 1) return 1;

  const ways = Array(n + 1).fill(0);
  ways[0] = 1;
  ways[1] = 1;

  for (let i = 2; i <= n; i++) {
    ways[i] = ways[i - 1] + ways[i - 2];
  }

  return ways[n];
}

console.log(climbStairs(2)); // 2
console.log(climbStairs(5)); // 8
```

For the stair-climbing problem where you can take 1 or 2 steps, complete the recurrence:

ways[i] = ways[i - 1] + ____

The DP checklist

Dynamic programming is useful when a problem has both of these properties:

1. Overlapping subproblems

The same smaller questions appear multiple times.

Example: fib(6) needs fib(5) and fib(4), and fib(5) also needs fib(4).

2. Optimal substructure

The answer to the larger problem can be built from answers to smaller problems.

For easy and medium data structure problems, look for phrases like:

• number of ways
• maximum or minimum cost
• best score up to index i
• can we reach this state?
• longest or shortest valid sequence

Then define the subproblem clearly before writing code.

What you should keep

Recursion and dynamic programming are not separate tricks. They are connected ways to reason about smaller subproblems.

Key ideas:

• Recursion needs a base case and a recursive case.
• Recursive calls use the call stack, so depth affects space.
• Naive recursion can repeat the same work many times.
• Memoization is top-down DP using a cache, often a Map.
• Tabulation is bottom-up DP using an array or table.
• Before coding DP, define what one state means.

In the next lesson, Practice Problems and Case Studies, you will apply these patterns alongside the data structures and algorithms from the full course.