Source: https://leetcode.com/problems/climbing-stairs/

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

/**
* @param {number} n
* @return {number}
*/
// Approach 1: Similar to fibonacci recursion
// Recursively climb 1 stair or 2 stairs at a time
// Base case
// n === 1 => 1
// n === 2 => 2
// Recursive step
// n > 2 => climbStairs(n-1) going up 1 step at a time + climbStairs(n-2) going up 2 steps at a time
// Time: O(2^n) since at each step we recursively make 2 choices; Space: O(n)
// This will be too slow especially as n grows large - lead to recursion stack overflows potentially
var climbStairs = function(n) {  
 if (n === 1) {
   return 1;
 }
 if (n === 2) {
   return 2;
 }
 
 return climbStairs(n - 1) + climbStairs(n - 2);
}