62 likes
·
1.5K reads
3 comments
The complexity of the provided solution is exponential, because you branch 3 times in each recursive call, the complexity is about O(3^n) wich is very bad and will not scale at all for any large N.
A very simple fix is using memoization.
You can change the function a bit to accept the nber of remaining steps, in that case you can think about it as "what's the possible ways to solve x steps" that way you can save the solution to that x in a global map (would be a closure in a real world app) and when you enter the function you check if you already know the solution to x, you just return the value. Pretty much like memoizing the calculation of Fibonacci numbers.
Yes, excellent point! memo works really well with recursion.
Here is the solution to staircase problem using memoization: indepthjavascript.dev/how-to-solve-the-sta…