Recursive Approach

From DP signals to recursive shape

In Introduction to Dynamic Programming, you learned to spot two important signals: repeated work and overlapping subproblems.

Now we’ll build the raw form those signals usually come from: a recursive approach.

Before memoization, before top-down DP, and before bottom-up tables, we need to answer:

• What is the smaller version of this problem?
• What choices can I make from the current state?
• When should the recursion stop?

Think of recursion as the first draft of a DP solution: not always efficient, but extremely useful for discovering the structure.

A recursive function needs a contract

A good recursive solution is not just “call the function again.” It has a clear contract.

A useful template:

function solve(state):
  if state is finished:
    return known answer

  answer = combine results from smaller states
  return answer

The important word is state.

For a full stack engineer, this is similar to defining an API endpoint contract: given these inputs, what does this function promise to return?

For recursion, the state might be:

• An index in an array
• A remaining amount
• A grid coordinate
• A string position
• A pair like (i, j)

Once the state is clear, the recurrence usually becomes easier to write.

The classic recursive draft

Fibonacci is overused, but it is perfect for seeing the recursive approach clearly.

The contract:

fib(n) returns the nth Fibonacci number.

Base cases:

• fib(0) = 0
• fib(1) = 1

Recursive case:

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

This version is intentionally naive. We are not improving it yet — we are learning how to express the problem recursively.

```javascript
let calls = 0;

function fib(n) {
  calls++;

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

  return fib(n - 1) + fib(n - 2);
}

const n = 6;
console.log(`fib(${n}) =`, fib(n));
console.log("recursive calls:", calls);
```

Which set of ingredients best describes a well-formed recursive solution?

Recursion shows the work

The recursive version of Fibonacci creates a tree of calls:

fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

Notice that fib(3) and fib(2) appear more than once.

That is the repeated work signal from the previous lesson showing up in a concrete form.

For this lesson, the point is not to fix it yet. The point is to see how recursion exposes the shape of the problem: a tree of smaller decisions or subproblems.

For climbing stairs where you can take either 1 or 2 steps, complete the recurrence:

ways(n) = ______

Assume the base cases are handled separately.

Recursion is not just Fibonacci

Consider a robot moving through a grid from the top-left to the bottom-right.

Allowed moves:

• Down
• Right

The contract:

countPaths(row, col) returns the number of ways to reach the destination from this cell.

Base cases:

• If we are at the destination, return 1.
• If we move outside the grid, return 0.

Recursive case:

• Paths from here = paths going down + paths going right.

```javascript
function countPaths(row, col, rows, cols) {
  const atDestination = row === rows - 1 && col === cols - 1;
  if (atDestination) return 1;

  const outOfBounds = row >= rows || col >= cols;
  if (outOfBounds) return 0;

  const goDown = countPaths(row + 1, col, rows, cols);
  const goRight = countPaths(row, col + 1, rows, cols);

  return goDown + goRight;
}

console.log("3x3 grid paths:", countPaths(0, 0, 3, 3));
console.log("2x4 grid paths:", countPaths(0, 0, 2, 4));
```

True or false:

If a recursive solution returns the correct answer, it is automatically efficient enough for large inputs.

What recursion costs

Recursive solutions are often expressive, but they are not free.

Key costs to watch:

• Call stack depth: each unfinished call stays on the stack.
• Repeated branches: the same state may be recomputed many times.
• Exponential growth: two or more branches per call can explode quickly.
• Debug complexity: state changes across nested calls can be hard to trace.

In production JavaScript, you also need to remember that very deep recursion can hit stack limits. For interview-style DP problems, recursion is still a powerful first model because it reveals the state and transitions cleanly.

Recursion often models choices

Many DP-style problems can be drafted recursively by asking:

At this state, what choices do I have?

Example: count the number of ways to make an amount using coin denominations.

At each state, we can choose to:

• Use the current coin again
• Skip to the next coin

The state is (index, remaining):

• index: which coin we are considering
• remaining: amount left to build

This is still plain recursion. In the next lesson, we’ll look at how to avoid recomputing the same states.

```javascript
function countWays(coins, index, remaining) {
  if (remaining === 0) return 1;
  if (remaining < 0) return 0;
  if (index === coins.length) return 0;

  const useCurrentCoin = countWays(coins, index, remaining - coins[index]);
  const skipCurrentCoin = countWays(coins, index + 1, remaining);

  return useCurrentCoin + skipCurrentCoin;
}

const coins = [1, 2, 5];
const amount = 5;

console.log(`ways to make ${amount}:`, countWays(coins, 0, amount));
```