## DEV Community is a community of 852,088 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Improving big o in climbing stairs (recursion) with memoization

In the climbing stairs problem (leetcode), we are asked to find in how many ways we can climb a set of stairs either taking one step or two steps. So to climb a set of 3 stairs we can take 3 one steps, or 1 step and then a 2 step, or a 2 step and then 1 step.

The way this problem is solved is by building a 'binary tree' where we add either 1 or 2 to the current step. Each recursion is a leaf on the tree.

``````               (step,target)
[0,3]
/         \
[1,3]        [2,3]
/    \        /
[2,3]  [3,3]   [3,3]
/
[3, 3]
``````

So we use two recursions every time well call the function and each one is a 'branch' of the tree. In one of the recursions we add 1 step and in the other one add 2 steps and whenever we find we reached the target step level or the 'top of the stairs' we return 1 and so the count of ways to reach the target increases. There are many recursions happening as the time complexity is very high at O(2^n).

``````const recursionTreeSlow = (topStair) => {
return recursion_Tree_Slow(0, topStair)
}

const recursion_Tree_Slow = (currentStair, topStair) => {
if(currentStair> topStair){
return 0
}
if(currentStair=== topStair){
return 1
}
let countWaysOfClimbing = recursion_Tree_Slow(currentStair+1, topStair) + recursion_Tree_Slow(currentStair+2, topStair)
return countWaysOfClimbing
}
``````

This solution works by 'brute force' traveling to every node once or calling a recursive function for every leaf in the tree, but if we can store the data somehow and reuse old recursions that are the same as the pattern repeats in the tree, we can improve the algorithm and with the help of a `memo` key-value pair data structure, can achieve this.

I should mention that I gave some intuitive names to the variables in this example, to try and make this more accessible to other people with a non-CS background like me (self-taught or bootcamp), but please let me know if this helps or not :)

## First let's review the variables

Comparing to leetcode I did:

• iteration index: `i` (`currentStair`)
• the passed argument `n` (`topStair`) which is the depth of the tree and in this example how many steps we need to climb
• the `memo` object (`treeData`).

But `i`, `n`, and `memo` are the traditional variable names used in these types of problems.

## Memoization

To improve the runtime of this problem we 'memoize' the data and eliminate unnecessary operations. So the key (`currentStair` ) will represent the current step to the target and the value (`countOfWaysToClimb`) is the count of different ways to reach the target from that stair.

`````` treeData[currentStair] = countOfWaysToClimb
``````

The object `treeData` serves to store and access the node values in a key-value pair structure and nodes that have the same values will be the same and won't be recreated.

Especifically on this example:

``````                  (step, target)
[0,4]
/            \
[1,4]            [2,4]
/       \           /    \
[2,4]       [3,4]    [3,4]  [4,4]
/    \        /       /
[3, 4] [4,4]   [4,4]    [4,4]
/
[4,4]
``````

The node `[2,4]` repeats twice so whenever we arrive at the right `[2,4]` node we already know the results of the subsequent recursions, knowing that there will be 2 ways to reach `[4,4]`. Because we already have a `currentStair` of 2 in the `dataObject`.

``````const recursionTreeMemoization = (topStair) => {
const treeData = {}
return recursion(0, topStair, treeData)
}

const recursion = (currentStair, topStair, treeData) => {
if (currentStair> topStair){
return 0
}
if (currentStair=== topStair){
return 1
}
if (treeData[currentStair] > 0){
return treeData[currentStair]
}
treeData[currentStair] = recursion(currentStair+ 1, topStair, treeData) + recursion(currentStair+ 2,topStair, treeData)

return treeData[currentStair]
}
``````

So the whenever `treeData[currentStair] > 0` is true it means that we already have a count of ways from that current stair stored in our `treeData` data object. So we just recall that count and add it to the current count and to accumulate the count.

Please feel more than welcome to reach out!