Recursive Staircase Problem

/**
 * Recursive Staircase Problem (Brute Force Solution).
 *
 * @param {number} stairsNum - Number of stairs to climb on.
 * @return {number} - Number of ways to climb a staircase.
 */
export default function recursiveStaircaseBF(stairsNum) {
  if (stairsNum <= 0) {
    // There is no way to go down - you climb the stairs only upwards.
    // Also if you're standing on the ground floor that you don't need to do any further steps.
    return 0;
  }

  if (stairsNum === 1) {
    // There is only one way to go to the first step.
    return 1;
  }

  if (stairsNum === 2) {
    // There are two ways to get to the second steps: (1 + 1) or (2).
    return 2;
  }

  // Sum up how many steps we need to take after doing one step up with the number of
  // steps we need to take after doing two steps up.
  return recursiveStaircaseBF(stairsNum - 1) + recursiveStaircaseBF(stairsNum - 2);
}

/**
 * Recursive Staircase Problem (Dynamic Programming Solution).
 *
 * @param {number} stairsNum - Number of stairs to climb on.
 * @return {number} - Number of ways to climb a staircase.
 */
export default function recursiveStaircaseDP(stairsNum) {
  if (stairsNum < 0) {
    // There is no way to go down - you climb the stairs only upwards.
    return 0;
  }

  // Init the steps vector that will hold all possible ways to get to the corresponding step.
  const steps = new Array(stairsNum + 1).fill(0);

  // Init the number of ways to get to the 0th, 1st and 2nd steps.
  steps[0] = 0;
  steps[1] = 1;
  steps[2] = 2;

  if (stairsNum <= 2) {
    // Return the number of ways to get to the 0th or 1st or 2nd steps.
    return steps[stairsNum];
  }

  // Calculate every next step based on two previous ones.
  for (let currentStep = 3; currentStep <= stairsNum; currentStep += 1) {
    steps[currentStep] = steps[currentStep - 1] + steps[currentStep - 2];
  }

  // Return possible ways to get to the requested step.
  return steps[stairsNum];
}

/**
 * Recursive Staircase Problem (Iterative Solution).
 *
 * @param {number} stairsNum - Number of stairs to climb on.
 * @return {number} - Number of ways to climb a staircase.
 */
export default function recursiveStaircaseIT(stairsNum) {
  if (stairsNum <= 0) {
    // There is no way to go down - you climb the stairs only upwards.
    // Also you don't need to do anything to stay on the 0th step.
    return 0;
  }

  // Init the number of ways to get to the 0th, 1st and 2nd steps.
  const steps = [1, 2];

  if (stairsNum <= 2) {
    // Return the number of possible ways of how to get to the 1st or 2nd steps.
    return steps[stairsNum - 1];
  }

  // Calculate the number of ways to get to the n'th step based on previous ones.
  // Comparing to Dynamic Programming solution we don't store info for all the steps but
  // rather for two previous ones only.
  for (let currentStep = 3; currentStep <= stairsNum; currentStep += 1) {
    [steps[0], steps[1]] = [steps[1], steps[0] + steps[1]];
  }

  // Return possible ways to get to the requested step.
  return steps[1];
}

/**
 * Recursive Staircase Problem (Recursive Solution With Memoization).
 *
 * @param {number} totalStairs - Number of stairs to climb on.
 * @return {number} - Number of ways to climb a staircase.
 */
export default function recursiveStaircaseMEM(totalStairs) {
  // Memo table that will hold all recursively calculated results to avoid calculating them
  // over and over again.
  const memo = [];

  // Recursive closure.
  const getSteps = (stairsNum) => {
    if (stairsNum <= 0) {
      // There is no way to go down - you climb the stairs only upwards.
      // Also if you're standing on the ground floor that you don't need to do any further steps.
      return 0;
    }

    if (stairsNum === 1) {
      // There is only one way to go to the first step.
      return 1;
    }

    if (stairsNum === 2) {
      // There are two ways to get to the second steps: (1 + 1) or (2).
      return 2;
    }

    // Avoid recursion for the steps that we've calculated recently.
    if (memo[stairsNum]) {
      return memo[stairsNum];
    }

    // Sum up how many steps we need to take after doing one step up with the number of
    // steps we need to take after doing two steps up.
    memo[stairsNum] = getSteps(stairsNum - 1) + getSteps(stairsNum - 2);

    return memo[stairsNum];
  };

  // Return possible ways to get to the requested step.
  return getSteps(totalStairs);
}