# How the Recursive Staircase Solution Uses Dynamic Programming Memoization

> Learn how the recursive staircase dynamic programming solution employs memoization to optimize performance. Slash complexity from O(2ⁿ) to O(n) by solving subproblems just once.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: deep-dive
- Published: 2026-02-24

---

**The recursive staircase dynamic programming solution uses a top-down memoization cache to store intermediate results, reducing time complexity from O(2ⁿ) to O(n) by ensuring each subproblem is solved only once.**

The `trekhleb/javascript-algorithms` repository demonstrates this classic optimization technique through the staircase climbing problem, where the goal is to count distinct ways to reach the *n*th step when taking either 1 or 2 steps at a time. By caching results in a `memo` array, the algorithm avoids redundant calculations inherent in pure recursion.

## Understanding the Recursive Staircase Problem

The staircase problem asks for the number of distinct ways to climb *n* steps given that you can move either 1 or 2 steps at a time. Without optimization, a naive recursive approach explores every possible combination of steps, resulting in exponential time complexity of **O(2ⁿ)** due to repeated calculations of the same subproblems.

The **dynamic programming (DP) version** eliminates this redundancy through **memoization**, storing the result of each subproblem so it is computed only once.

## Top-Down Dynamic Programming with Memoization

The implementation follows a top-down recursive strategy with a cache lookup pattern. According to the source code in [`src/algorithms/uncategorized/recursive-staircase/recursiveStaircaseDP.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/src/algorithms/uncategorized/recursive-staircase/recursiveStaircaseDP.js), the algorithm initializes a storage mechanism before executing the recursive logic.

### Initializing the Memoization Cache

The function creates an array named `memo` with a length of `n + 1`, filling each index with `undefined` or `null` to indicate uncomputed states. This array serves as the lookup table for previously calculated step combinations.

### Setting Base Cases

The algorithm seeds the cache with known values to terminate recursion:

- `memo[0] = 1` — Represents the "do nothing" way to stay at ground level
- `memo[1] = 1` — Represents the single way to climb one step

These base cases prevent infinite recursion and provide the foundation for building larger solutions.

### The Recursive Logic

For any given `steps` value, the algorithm first checks whether `memo[steps]` contains a cached result. If the value exists, it returns immediately without further recursion.

If the value is not cached, the function recursively computes the sum of ways to reach `steps - 1` and `steps - 2`, stores this sum in `memo[steps]`, and then returns the result. This ensures that subsequent calls with the same `steps` argument retrieve the value in **O(1)** time.

## Implementation in JavaScript

The following example demonstrates how to use the memoized implementation from the repository:

```javascript
// Import the DP implementation with memoization
import recursiveStaircaseDP from './src/algorithms/uncategorized/recursive-staircase/recursiveStaircaseDP';

// Calculate ways to climb 5 steps
const ways = recursiveStaircaseDP(5);
console.log(`Ways to climb 5 steps: ${ways}`); // Output: 8

// Integration in a React component
function StaircaseCounter({ steps }) {
  const [count, setCount] = React.useState(0);
  
  React.useEffect(() => {
    setCount(recursiveStaircaseDP(steps));
  }, [steps]);
  
  return <div>{`There are ${count} ways to climb ${steps} steps.`}</div>;
}

```

The core logic in [`recursiveStaircaseDP.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseDP.js) implements the memoization pattern by checking the cache before computation and populating it with the result of `recursiveStaircaseDP(steps - 1) + recursiveStaircaseDP(steps - 2)`.

## Performance Analysis

The memoized approach transforms the algorithm's complexity characteristics:

- **Time Complexity**: **O(n)** — Each value from 0 to *n* is calculated exactly once
- **Space Complexity**: **O(n)** — Required for the `memo` array and the recursion call stack

This contrasts sharply with the brute-force implementation in [`recursiveStaircaseBF.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseBF.js), which recalculates the same subproblems exponentially and becomes infeasible for large *n*.

## Alternative Implementations in the Repository

The `trekhleb/javascript-algorithms` repository provides several variations of this solution for comparison:

- **[`recursiveStaircaseMEM.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseMEM.js)** — Uses a JavaScript object (hash map) instead of an array for the memoization cache, offering similar O(n) performance with potentially different constant factors
- **[`recursiveStaircaseIT.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseIT.js)** — Implements the bottom-up **tabulation** approach without recursion, building the solution iteratively from the base cases upward
- **[`recursiveStaircaseBF.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseBF.js)** — Contains the pure recursive brute-force solution used to demonstrate the performance impact of omitting memoization

These files are located in `src/algorithms/uncategorized/recursive-staircase/` and collectively illustrate the progression from exponential recursive solutions to efficient dynamic programming techniques.

## Summary

- The **recursive staircase dynamic programming** solution uses a `memo` array to cache intermediate results, converting an O(2ⁿ) algorithm into an O(n) solution
- **Top-down memoization** checks the cache before computing and stores results immediately after calculation
- Base cases `memo[0] = 1` and `memo[1] = 1` provide the termination conditions for the recursion
- The implementation in [`recursiveStaircaseDP.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseDP.js) demonstrates the classic pattern of recursive DP with memoization
- Alternative implementations in the repository showcase object-based memoization and iterative tabulation approaches

## Frequently Asked Questions

### What is the time complexity of the memoized recursive staircase solution?

The memoized solution runs in **O(n)** time complexity because each subproblem (from 0 to *n*) is solved exactly once and stored in the cache. Subsequent lookups for the same step count return in constant time, eliminating the redundant calculations present in the O(2ⁿ) brute-force approach.

### How does memoization differ from tabulation in the staircase problem?

**Memoization** (top-down) uses recursion and checks a cache before computing, storing results as they are calculated naturally by the recursive calls. **Tabulation** (bottom-up), as implemented in [`recursiveStaircaseIT.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseIT.js), iteratively fills an array starting from the base cases and building up to *n* without recursive function calls, typically offering better constant factors and eliminating stack overflow risks for large *n*.

### Why is memo[0] set to 1 in the recursive staircase algorithm?

`memo[0]` is set to **1** to represent the single way to remain at ground level (the "do nothing" approach). This mathematical convention ensures that when computing `memo[2] = memo[1] + memo[0]`, the result correctly equals 2 (two ways: two single steps or one double step), maintaining consistency with the Fibonacci-like recurrence relation governing the problem.

### Can the recursive staircase memoization be optimized for space?

Yes, the space complexity can be reduced to **O(1)** by recognizing that only the previous two values are needed to calculate the current step count. While the memoized recursive approach in [`recursiveStaircaseDP.js`](https://github.com/trekhleb/javascript-algorithms/blob/main/recursiveStaircaseDP.js) uses O(n) space for the cache and call stack, an iterative implementation can maintain just two variables to track `steps - 1` and `steps - 2`, eliminating the need for the full array.