Self taught full stack developer who loves to code, just for fun. Enjoys health & fitness, yoga, and meditation. Lives with his wonderful wife and 2 cats in Abington, PA.
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.
Amr Saber
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.