Recursive Staircase

Definition

Definition

The Recursive Staircase Algorithm (Fibonacci) is a dynamic programming approach to efficiently solve the problem of finding the number of ways to climb a staircase with a given number of steps, where you can take either 1 or 2 steps at a time. It optimizes the computation by storing previously calculated results, avoiding redundant calculations

Explanation

It calculates the number of ways to climb a staircase with n steps by recursively breaking down the problem into smaller subproblems. At each step, it considers two possibilities: either taking one step or taking two steps. It then sums up the results of these two possibilities to find the total number of ways to climb n steps. By memoizing previously computed results, it avoids redundant calculations and optimizes the overall computation.

Guidance

• Base cases
  • if n is 0 or 1, there is only one way to climb the staircase (either by taking no steps or taking one step)
• If the result for n is already computed (memoized), return it
  • Otherwise, recursively compute the number of ways to climb n-1 steps and n-2 steps
  • Memoize the result for n
  • Return the sum of the results computed for n-1 and n-2

Tips

• utilize memoization to store previously computed results and avoid redundant calculations, significantly improving efficiency
• start by considering the base cases (0 and 1 steps) to build the recursive solution from the ground up
• be cautious of potential stack overflow issues with deep recursion for large values of n; consider optimizing with iterative approaches or tail recursion if necessary

Practice

Practice

countWays(n):
  if n <= 1:
    return 1  # Base cases

  if memo[n] is not None:
    return memo[n]  # Return memoized result if available

  # Recursive calls
  memo[n] = countWays(n-1) + countWays(n-2)

  return memo[n]

# Initialize memoization array
memo = [None] * (max_steps + 1)

Solution

package main

func recursiveStaircaseBruteforce(stairsNum int) int {
	if stairsNum <= 0 {
		return 0
	}

	if stairsNum == 1 || stairsNum == 2 {
		return stairsNum
	}

	return recursiveStaircaseBruteforce(stairsNum-1) + recursiveStaircaseBruteforce(stairsNum-2)
}

func recursiveStaircaseIterative(stairsNum int) int {
	if stairsNum <= 0 {
		return 0
	}

	steps := []int{1, 2}

	if stairsNum <= 2 {
		return steps[stairsNum-1]
	}

	for currentStep := 3; currentStep <= stairsNum; currentStep++ {
		steps[0], steps[1] = steps[1], steps[0]+steps[1]
	}

	return steps[1]
}

func recursiveStaircaseDynamicProgramming(stairsNum int) int {
	if stairsNum < 0 {
		return 0
	}

	steps := make([]int, stairsNum+1)

	steps[0] = 0
	steps[1] = 1
	steps[2] = 2

	if stairsNum <= 2 {
		return steps[stairsNum]
	}

	for currentStep := 3; currentStep <= stairsNum; currentStep++ {
		steps[currentStep] = steps[currentStep-1] + steps[currentStep-2]
	}

	return steps[stairsNum]
}

func recursiveStaircaseMemoization(totalStairs int) int {
	memo := make([]int, totalStairs+1)

	var getSteps func(int) int
	getSteps = func(stairsNum int) int {
		if stairsNum <= 0 {
			return 0
		}

		if stairsNum == 1 || stairsNum == 2 {
			return stairsNum
		}

		if memo[stairsNum] != 0 {
			return memo[stairsNum]
		}

		memo[stairsNum] = getSteps(stairsNum-1) + getSteps(stairsNum-2)

		return memo[stairsNum]
	}

	return getSteps(totalStairs)
}

import java.util.HashMap;
import java.util.Map;

public class Main {

  public static int recursiveStaircaseBruteforce(int stairsNum) {
    if (stairsNum <= 0) {
      return 0;
    }

    if (stairsNum == 1 || stairsNum == 2) {
      return stairsNum;
    }

    return recursiveStaircaseBruteforce(stairsNum - 1) +
        recursiveStaircaseBruteforce(stairsNum - 2);
  }

  public static int recursiveStaircaseIterative(int stairsNum) {
    if (stairsNum <= 0) {
      return 0;
    }

    int[] steps = {1, 2};

    if (stairsNum <= 2) {
      return steps[stairsNum - 1];
    }

    for (int currentStep = 3; currentStep <= stairsNum; currentStep++) {
      int temp = steps[0];
      steps[0] = steps[1];
      steps[1] = temp + steps[1];
    }

    return steps[1];
  }

  public static int recursiveStaircaseDynamicProgramming(int stairsNum) {
    if (stairsNum < 0) {
      return 0;
    }

    int[] steps = new int[stairsNum + 1];

    steps[0] = 0;
    steps[1] = 1;
    steps[2] = 2;

    if (stairsNum <= 2) {
      return steps[stairsNum];
    }

    for (int currentStep = 3; currentStep <= stairsNum; currentStep++) {
      steps[currentStep] = steps[currentStep - 1] + steps[currentStep - 2];
    }

    return steps[stairsNum];
  }

  public static int recursiveStaircaseMemoization(int totalStairs) {
    Map<Integer, Integer> memo = new HashMap<>();

    return getSteps(totalStairs, memo);
  }

  private static int getSteps(int stairsNum, Map<Integer, Integer> memo) {
    if (stairsNum <= 0) {
      return 0;
    }

    if (stairsNum == 1 || stairsNum == 2) {
      return stairsNum;
    }

    if (memo.containsKey(stairsNum)) {
      return memo.get(stairsNum);
    }

    int result = getSteps(stairsNum - 1, memo) + getSteps(stairsNum - 2, memo);
    memo.put(stairsNum, result);

    return result;
  }
}

function recursiveStaircaseBruteforce(stairsNum) {
  if (stairsNum <= 0) {
    return 0;
  }

  if (stairsNum === 1 || stairsNum === 2) {
    return stairsNum;
  }

  return (
    recursiveStaircaseBruteforce(stairsNum - 1) +
    recursiveStaircaseBruteforce(stairsNum - 2)
  );
}

function recursiveStaircaseIterative(stairsNum) {
  if (stairsNum <= 0) {
    return 0;
  }

  const steps = [1, 2];

  if (stairsNum <= 2) {
    return steps[stairsNum - 1];
  }

  for (let currentStep = 3; currentStep <= stairsNum; currentStep += 1) {
    [steps[0], steps[1]] = [steps[1], steps[0] + steps[1]];
  }

  return steps[1];
}

function recursiveStaircaseDynamicProgramming(stairsNum) {
  if (stairsNum < 0) {
    return 0;
  }

  const steps = new Array(stairsNum + 1).fill(0);

  steps[0] = 0;
  steps[1] = 1;
  steps[2] = 2;

  if (stairsNum <= 2) {
    return steps[stairsNum];
  }

  for (let currentStep = 3; currentStep <= stairsNum; currentStep += 1) {
    steps[currentStep] = steps[currentStep - 1] + steps[currentStep - 2];
  }

  return steps[stairsNum];
}

function recursiveStaircaseMemoization(totalStairs) {
  const memo = [];

  const getSteps = (stairsNum) => {
    if (stairsNum <= 0) {
      return 0;
    }

    if (stairsNum === 1 || stairsNum === 2) {
      return stairsNum;
    }

    if (memo[stairsNum]) {
      return memo[stairsNum];
    }

    memo[stairsNum] = getSteps(stairsNum - 1) + getSteps(stairsNum - 2);

    return memo[stairsNum];
  };

  return getSteps(totalStairs);
}

fun recursiveStaircaseBruteforce(stairsNum: Int): Int {
    if (stairsNum <= 0) {
        return 0
    }
    if (stairsNum == 1 || stairsNum == 2) {
        return stairsNum
    }
    return recursiveStaircaseBruteforce(stairsNum - 1) + recursiveStaircaseBruteforce(stairsNum - 2)
}

fun recursiveStaircaseIterative(stairsNum: Int): Int {
    if (stairsNum <= 0) {
        return 0
    }
    val steps = intArrayOf(1, 2)
    if (stairsNum <= 2) {
        return steps[stairsNum - 1]
    }
    for (currentStep in 3..stairsNum) {
        steps[0] = steps[1].also { steps[1] += steps[0] }
    }
    return steps[1]
}

fun recursiveStaircaseDynamicProgramming(stairsNum: Int): Int {
    if (stairsNum < 0) {
        return 0
    }
    val steps = IntArray(stairsNum + 1) { 0 }
    steps[1] = 1
    steps[2] = 2
    if (stairsNum <= 2) {
        return steps[stairsNum]
    }
    for (currentStep in 3..stairsNum) {
        steps[currentStep] = steps[currentStep - 1] + steps[currentStep - 2]
    }
    return steps[stairsNum]
}

fun recursiveStaircaseMemoization(totalStairs: Int): Int {
    val memo = mutableMapOf<Int, Int>()

    fun getSteps(stairsNum: Int): Int {
        if (stairsNum <= 0) {
            return 0
        }
        if (stairsNum == 1 || stairsNum == 2) {
            return stairsNum
        }
        if (memo.containsKey(stairsNum)) {
            return memo[stairsNum]!!
        }
        memo[stairsNum] = getSteps(stairsNum - 1) + getSteps(stairsNum - 2)
        return memo[stairsNum]!!
    }

    return getSteps(totalStairs)
}

def recursive_staircase_bruteforce(stairs_num):
    if stairs_num <= 0:
        return 0
    if stairs_num == 1 or stairs_num == 2:
        return stairs_num
    return (recursive_staircase_bruteforce(stairs_num - 1) +
            recursive_staircase_bruteforce(stairs_num - 2))


def recursive_staircase_iterative(stairs_num):
    if stairs_num <= 0:
        return 0
    steps = [1, 2]
    if stairs_num <= 2:
        return steps[stairs_num - 1]
    for current_step in range(3, stairs_num + 1):
        steps[0], steps[1] = steps[1], steps[0] + steps[1]
    return steps[1]


def recursive_staircase_dynamic_programming(stairs_num):
    if stairs_num < 0:
        return 0
    steps = [0] * (stairs_num + 1)
    steps[1] = 1
    steps[2] = 2
    if stairs_num <= 2:
        return steps[stairs_num]
    for current_step in range(3, stairs_num + 1):
        steps[current_step] = steps[current_step - 1] + steps[current_step - 2]
    return steps[stairs_num]


def recursive_staircase_memoization(total_stairs):
    memo = {}

    def get_steps(stairs_num):
        if stairs_num <= 0:
            return 0
        if stairs_num == 1 or stairs_num == 2:
            return stairs_num
        if stairs_num in memo:
            return memo[stairs_num]
        memo[stairs_num] = get_steps(stairs_num - 1) + get_steps(stairs_num - 2)
        return memo[stairs_num]

    return get_steps(total_stairs)

fn recursive_staircase_bruteforce(stairs_num: i32) -> i32 {
    if stairs_num <= 0 {
        return 0;
    }
    if stairs_num == 1 || stairs_num == 2 {
        return stairs_num;
    }
    recursive_staircase_bruteforce(stairs_num - 1) + recursive_staircase_bruteforce(stairs_num - 2)
}

fn recursive_staircase_iterative(stairs_num: i32) -> i32 {
    if stairs_num <= 0 {
        return 0;
    }
    let mut steps = vec![1, 2];
    if stairs_num <= 2 {
        return steps[(stairs_num - 1) as usize];
    }
    for current_step in 3..=stairs_num {
        steps[0] = steps[1];
        steps[1] += steps[0];
    }
    steps[1]
}

fn recursive_staircase_dynamic_programming(stairs_num: i32) -> i32 {
    if stairs_num < 0 {
        return 0;
    }
    let mut steps = vec![0; (stairs_num + 1) as usize];
    steps[1] = 1;
    steps[2] = 2;
    if stairs_num <= 2 {
        return steps[stairs_num as usize];
    }
    for current_step in 3..=stairs_num {
        steps[current_step as usize] = steps[(current_step - 1) as usize] + steps[(current_step - 2) as usize];
    }
    steps[stairs_num as usize]
}

fn recursive_staircase_memoization(total_stairs: i32) -> i32 {
    let mut memo = vec![0; (total_stairs + 1) as usize];

    fn get_steps(stairs_num: i32, memo: &mut Vec<i32>) -> i32 {
        if stairs_num <= 0 {
            return 0;
        }
        if stairs_num == 1 || stairs_num == 2 {
            return stairs_num;
        }
        if memo[stairs_num as usize] != 0 {
            return memo[stairs_num as usize];
        }
        memo[stairs_num as usize] = get_steps(stairs_num - 1, memo) + get_steps(stairs_num - 2, memo);
        memo[stairs_num as usize]
    }

    get_steps(total_stairs, &mut memo)
}

function recursiveStaircaseBruteforce(stairsNum: number): number {
  if (stairsNum <= 0) {
    return 0;
  }

  if (stairsNum === 1 || stairsNum === 2) {
    return stairsNum;
  }

  return (
    recursiveStaircaseBruteforce(stairsNum - 1) +
    recursiveStaircaseBruteforce(stairsNum - 2)
  );
}

function recursiveStaircaseIterative(stairsNum: number): number {
  if (stairsNum <= 0) {
    return 0;
  }

  const steps: number[] = [1, 2];

  if (stairsNum <= 2) {
    return steps[stairsNum - 1];
  }

  for (let currentStep = 3; currentStep <= stairsNum; currentStep += 1) {
    [steps[0], steps[1]] = [steps[1], steps[0] + steps[1]];
  }

  return steps[1];
}

function recursiveStaircaseDynamicProgramming(stairsNum: number): number {
  if (stairsNum < 0) {
    return 0;
  }

  const steps: number[] = new Array(stairsNum + 1).fill(0);

  steps[0] = 0;
  steps[1] = 1;
  steps[2] = 2;

  if (stairsNum <= 2) {
    return steps[stairsNum];
  }

  for (let currentStep = 3; currentStep <= stairsNum; currentStep += 1) {
    steps[currentStep] = steps[currentStep - 1] + steps[currentStep - 2];
  }

  return steps[stairsNum];
}

function recursiveStaircaseMemoization(totalStairs: number): number {
  const memo: number[] = [];

  const getSteps = (stairsNum: number): number => {
    if (stairsNum <= 0) {
      return 0;
    }

    if (stairsNum === 1 || stairsNum === 2) {
      return stairsNum;
    }

    if (memo[stairsNum]) {
      return memo[stairsNum];
    }

    memo[stairsNum] = getSteps(stairsNum - 1) + getSteps(stairsNum - 2);

    return memo[stairsNum];
  };

  return getSteps(totalStairs);
}