Optimize Recursion with Memoization: Stair Climbing & DP

Mastering Recursion with Memoization: A Deep Dive into Stair Climbing and Dynamic Programming

This document explores the concept of memoization, a powerful optimization technique often referred to as caching, within the context of programming. We will use a practical example, the stair climbing problem, to illustrate how naive recursive solutions can become computationally prohibitive and how memoization effectively transforms these inefficient algorithms into efficient dynamic programming solutions.

The Stair Climbing Problem: Defining the Challenge

The stair climbing problem, at its core, is about finding the number of distinct ways to reach the top of a staircase given a set of allowed step sizes. Imagine a staircase with n steps. You can ascend by taking steps of specific lengths. For instance, you might be able to climb one, three, or five steps at a time. The objective is to determine the total number of unique sequences of these allowed step sizes that sum up to exactly n.

This problem shares a fundamental characteristic with other combinatorial problems, such as the classic frog hopping problem (where frogs can hop one or two steps). Both problems can be approached recursively by breaking them down into smaller, self-similar subproblems.

Recursive Formulation

Let f(n) represent the number of ways to climb n stairs. If we can take steps of sizes s1, s2, s3, ... sk, then the number of ways to reach step n is the sum of the number of ways to reach the preceding steps from which a valid final step can be taken.

Specifically, if the allowed step sizes are steps = {1, 3, 5}, then to reach step n, the last step taken must have been of size 1, 3, or 5.

• If the last step was of size 1, we must have been at step n-1. The number of ways to reach n-1 is f(n-1).
• If the last step was of size 3, we must have been at step n-3. The number of ways to reach n-3 is f(n-3).
• If the last step was of size 5, we must have been at step n-5. The number of ways to reach n-5 is f(n-5).

Therefore, the recursive relation is:

f(n) = f(n-1) + f(n-3) + f(n-5)

This formulation assumes that n-1, n-3, and n-5 are non-negative.

Base Cases

To make the recursion terminate, we need to define base cases:

• f(0) = 1: If there are zero steps, there is exactly one way to “climb” them: do nothing. This represents a successful path.
• f(n) < 0: If n becomes negative, it means we have overshot the target. This is not a valid path, so it contributes 0 ways.

Generalizing Step Sizes

The problem can be generalized to accommodate any set of allowed step sizes. If steps is a set of allowed step lengths, then:

f(n, steps) = sum(f(n - s, steps) for s in steps if n - s >= 0)

with the same base cases for f(0) and f(n < 0).

Naive Recursive Implementation and its Pitfalls

Let’s translate this recursive definition into a programming construct, specifically Python.

def step_count_recursive(n, steps={1, 3, 5}):
    """
    Calculates the number of ways to climb n stairs with given step sizes.
    This is a naive recursive implementation.
    """
    if n == 0:
        return 1
    if n < 0:
        return 0

    total_ways = 0
    for s in steps:
        total_ways += step_count_recursive(n - s, steps)
    return total_ways

# Example usage:
# print(step_count_recursive(10))

If we attempt to run this function with even moderately large values of n, we encounter significant performance issues.

The Problem of Redundant Computations

The core issue with this naive recursive approach is the exponential growth of redundant computations. Consider calculating step_count_recursive(6) with steps = {1, 3, 5}:

• step_count_recursive(6) calls:
  • step_count_recursive(5)
  • step_count_recursive(3)
  • step_count_recursive(1)
• step_count_recursive(5) calls:
  • step_count_recursive(4)
  • step_count_recursive(2)
  • step_count_recursive(0)
• step_count_recursive(3) calls:
  • step_count_recursive(2)
  • step_count_recursive(0)
  • step_count_recursive(-2) (returns 0)

Notice that step_count_recursive(2) is computed twice. As n increases, the number of overlapping subproblems grows dramatically. For n=10, the computation tree expands rapidly, leading to repeated calculations of the same step_count_recursive(k) for various k.

This phenomenon is often visualized as a computation tree. For small n, this tree is manageable. However, for larger n, the tree becomes excessively deep and wide, leading to:

1. Excessive Function Calls: The sheer number of recursive calls can overwhelm the call stack, leading to a RecursionError (maximum recursion depth exceeded).
2. Prohibitive Time Complexity: The time taken grows exponentially with n, making the solution impractical for anything beyond small inputs. For n=35, the computation can take several seconds. For n=40 or n=50, it becomes infeasible on standard hardware.

Demonstrating the Inefficiency

Let's consider a slightly more structured way to examine the recursive calls.

Example: f(6) with steps {1, 3, 5}

f(6)
|-- f(5)
|   |-- f(4)
|   |   |-- f(3)
|   |   |   |-- f(2)
|   |   |   |   |-- f(1) -> f(0)+f(-2)+f(-4) -> 1+0+0 = 1
|   |   |   |   |-- f(-1) -> 0
|   |   |   |   |-- f(-3) -> 0
|   |   |   |-- f(0) -> 1
|   |   |   |-- f(-2) -> 0
|   |   |-- f(1) -> f(0)+f(-2)+f(-4) -> 1+0+0 = 1
|   |   |-- f(-1) -> 0
|   |-- f(2)  <-- REPEATED COMPUTATION
|   |   |-- f(1) -> f(0)+f(-2)+f(-4) -> 1+0+0 = 1
|   |   |-- f(-1) -> 0
|   |   |-- f(-3) -> 0
|   |-- f(0) -> 1
|-- f(3)  <-- REPEATED COMPUTATION
|   |-- f(2)  <-- REPEATED COMPUTATION
|   |   |-- f(1) -> f(0)+f(-2)+f(-4) -> 1+0+0 = 1
|   |   |-- f(-1) -> 0
|   |   |-- f(-3) -> 0
|   |-- f(0) -> 1
|   |-- f(-2) -> 0
|-- f(1)  <-- REPEATED COMPUTATION
    |-- f(0) -> 1
    |-- f(-2) -> 0
    |-- f(-4) -> 0

In this simplified tree for f(6):

• f(3) is computed twice.
• f(2) is computed three times.
• f(1) is computed four times.
• f(0) is computed five times.

The size of this redundancy increases dramatically with n. The problem is not just that we are doing work multiple times; it's that the number of times we do that work grows exponentially.

Introducing Memoization: Caching the Results

Memoization is an optimization technique used to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. In essence, it's a form of caching applied to function results.

The core idea is: if a function is called with a particular set of arguments, and that function's output is deterministic (meaning it always produces the same output for the same input), we can store the (input, output) pair. If the function is called again with the same input, we retrieve the stored output instead of recomputing it.

How Memoization Addresses Redundancy

For the stair climbing problem, memoization directly tackles the issue of repeated subproblem calculations. We can maintain a data structure (like a dictionary or hash map) to store the results of step_count(k) for each k that has already been computed.

When step_count(k) is called:

1. Check if the result for k is already in the cache.
2. If it is, return the cached value immediately.
3. If it is not, compute the result recursively as before.
4. Before returning the computed result, store it in the cache associated with k.

This ensures that each unique subproblem step_count(k) is computed only once.

Implementing Memoization in Python

We can implement memoization by creating a wrapper function or by passing a cache (e.g., a dictionary) through the recursive calls. For clarity, we will create a separate function that incorporates a cache.

1. Initializing the Cache:
A dictionary is well-suited for this, mapping the number of steps (n) to the number of ways to climb them.

2. The Memoized Function:

def memoized_step_count(n, steps={1, 3, 5}, cache=None):
    """
    Calculates the number of ways to climb n stairs with given step sizes
    using memoization.
    """
    if cache is None:
        cache = {}

    # Base cases
    if n == 0:
        return 1
    if n < 0:
        return 0

    # Check if result is already in cache
    if n in cache:
        return cache[n]

    # Compute result if not in cache
    total_ways = 0
    for s in steps:
        total_ways += memoized_step_count(n - s, steps, cache)

    # Store the result in cache before returning
    cache[n] = total_ways
    return total_ways

# Example usage:
# print(memoized_step_count(10))
# print(memoized_step_count(35))

This version significantly improves performance. Let's analyze why.

The Power of Memoization: Performance Gains

The memoized version of step_count transforms the algorithm from one with exponential time complexity to one with polynomial time complexity.

Time and Space Complexity Analysis

• Naive Recursive Approach:
  • Time Complexity: O(k^n), where k is the number of possible step sizes. This is because each call can branch out k times, and the depth of recursion can be up to n.
  • Space Complexity: O(n) due to the recursion depth on the call stack.
• Memoized Approach:
  • Time Complexity: O(n * k), where n is the number of steps and k is the number of possible step sizes. This is because each value of n from 0 to n is computed only once. For each n, we iterate through the k possible step sizes.
  • Space Complexity: O(n) for the cache to store the results for each n, plus O(n) for the recursion stack depth. The dominant factor is O(n).

Demonstrating the Speedup

Let's use a simple timing mechanism to observe the difference.

import time

def time_function(func, *args, **kwargs):
    start_time = time.time()
    result = func(*args, **kwargs)
    end_time = time.time()
    elapsed_time = end_time - start_time
    print(f"Function: {func.__name__}, Args: {args}, Result: {result}, Time: {elapsed_time:.6f} seconds")
    return result

# Naive recursive function (defined earlier)
def step_count_recursive(n, steps={1, 3, 5}):
    if n == 0: return 1
    if n < 0: return 0
    total_ways = 0
    for s in steps:
        total_ways += step_count_recursive(n - s, steps)
    return total_ways

# Memoized function (defined earlier)
def memoized_step_count(n, steps={1, 3, 5}, cache=None):
    if cache is None: cache = {}
    if n == 0: return 1
    if n < 0: return 0
    if n in cache: return cache[n]
    total_ways = 0
    for s in steps:
        total_ways += memoized_step_count(n - s, steps, cache)
    cache[n] = total_ways
    return total_ways

# --- Timing Comparisons ---

print("--- Comparing Naive Recursion vs. Memoization ---")

# Small input where naive is still fast
print("\nInput: n=10")
time_function(step_count_recursive, 10)
time_function(memoized_step_count, 10)

# Medium input where the difference starts to show
print("\nInput: n=25")
time_function(step_count_recursive, 25) # This will be noticeably slower
time_function(memoized_step_count, 25)

# Larger input where naive becomes impractical
print("\nInput: n=35")
# time_function(step_count_recursive, 35) # This might take a very long time or crash
print("Skipping naive recursive for n=35 due to excessive computation time.")
time_function(memoized_step_count, 35)

# Very large input demonstrating memoization's scalability
print("\nInput: n=100")
# The naive version would never finish for n=100
print("Naive recursive version would not be able to compute n=100 in a reasonable time.")
time_function(memoized_step_count, 100)

Observations from Timing

• For small n (e.g., 10), both functions execute quickly, and the overhead of setting up the cache for the memoized version might even make it slightly slower.
• As n increases (e.g., 25), the naive recursive function begins to show a significant performance degradation, while the memoized version remains fast.
• For larger n (e.g., 35 or 100), the naive recursive function becomes impractical, taking seconds, minutes, or even failing due to stack overflow. The memoized version, however, computes the result almost instantaneously, even for extremely large inputs like n=100.

The results for n=100 with steps {1, 3, 5} are astronomical, in the quadrillions, but the memoized function computes this value rapidly because it avoids recalculating any subproblem.

Generalizing Memoization and Dynamic Programming

Memoization is a top-down approach to dynamic programming. Dynamic programming, in general, is an algorithmic paradigm that solves complex problems by breaking them down into simpler subproblems, solving each subproblem only once, and storing their solutions.

Top-Down (Memoization) vs. Bottom-Up (Tabulation)

Memoization is a "top-down" approach: we start with the main problem and recursively break it down, storing results as we go.

The "bottom-up" approach, often called tabulation, solves the subproblems first and then uses them to build up the solution to the main problem.

For the stair climbing problem, a bottom-up approach would look like this:

def tabulated_step_count(n, steps={1, 3, 5}):
    """
    Calculates the number of ways to climb n stairs with given step sizes
    using tabulation (bottom-up dynamic programming).
    """
    # dp[i] will store the number of ways to reach step i
    dp = [0] * (n + 1)

    # Base case: there is 1 way to reach step 0
    dp[0] = 1

    # Iterate from step 1 up to n
    for i in range(1, n + 1):
        # For each possible step size
        for s in steps:
            # If we can reach step i from step (i - s)
            if i - s >= 0:
                dp[i] += dp[i - s]

    return dp[n]

# Example usage:
# print(tabulated_step_count(10))
# print(tabulated_step_count(100))

Comparing Memoization and Tabulation

Feature	Memoization (Top-Down)	Tabulation (Bottom-Up)
Approach	Recursive, starts from the problem, works down.	Iterative, starts from base cases, works up.
State Storage	Uses a cache (e.g., dictionary) to store computed results.	Uses an array or table to store computed results.
Execution	Only computes states that are actually needed.	Computes all states from base cases up to the target.
Overhead	Function call overhead, cache lookup.	Loop overhead, array access.
Flexibility	Can be easier to implement from a recursive definition.	Can be more efficient if all subproblems are needed.
Stack Depth	Can still hit recursion depth limits for very large n.	No recursion depth issues.

For the stair climbing problem, both memoization and tabulation yield the same time complexity: O(n * k). Tabulation might have a slight edge in constant factors due to avoiding function call overhead and potentially better cache locality with arrays. However, memoization is often more intuitive to derive directly from a recursive problem definition.

Handling Variable Step Sizes

The implementation can be further generalized to accept arbitrary step sizes.

def memoized_step_count_general(n, allowed_steps):
    """
    Calculates the number of ways to climb n stairs with a given set of allowed step sizes,
    using memoization.
    """
    cache = {}

    def helper(current_n):
        if current_n == 0:
            return 1
        if current_n < 0:
            return 0

        if current_n in cache:
            return cache[current_n]

        total_ways = 0
        for step in allowed_steps:
            total_ways += helper(current_n - step)

        cache[current_n] = total_ways
        return total_ways

    return helper(n)

def tabulated_step_count_general(n, allowed_steps):
    """
    Calculates the number of ways to climb n stairs with a given set of allowed step sizes,
    using tabulation.
    """
    dp = [0] * (n + 1)
    dp[0] = 1

    for i in range(1, n + 1):
        for step in allowed_steps:
            if i - step >= 0:
                dp[i] += dp[i - step]
    return dp[n]

# Example usage:
steps_1_3_5 = {1, 3, 5}
steps_1_2 = {1, 2} # Fibonacci sequence related

print("\n--- General Step Sizes ---")
print(f"N=10, Steps={steps_1_3_5}:")
print(f"  Memoized: {memoized_step_count_general(10, steps_1_3_5)}")
print(f"  Tabulated: {tabulated_step_count_general(10, steps_1_3_5)}")

print(f"\nN=10, Steps={steps_1_2}:")
print(f"  Memoized: {memoized_step_count_general(10, steps_1_2)}")
print(f"  Tabulated: {tabulated_step_count_general(10, steps_1_2)}")

print(f"\nN=20, Steps={steps_1_2}:")
print(f"  Memoized: {memoized_step_count_general(20, steps_1_2)}")
print(f"  Tabulated: {tabulated_step_count_general(20, steps_1_2)}")

This generalized approach highlights the versatility of memoization and tabulation in solving problems that exhibit optimal substructure and overlapping subproblems.

Conclusion: The Efficiency of Caching

Memoization, or caching function results, is a fundamental technique for optimizing recursive algorithms that suffer from redundant computations. By storing and reusing the results of expensive function calls with identical inputs, we can transform algorithms with exponential time complexity into efficient polynomial-time solutions.

The stair climbing problem serves as an excellent, tangible example of this principle. A naive recursive solution quickly becomes intractable as the number of stairs increases. However, by applying memoization (top-down dynamic programming) or tabulation (bottom-up dynamic programming), we can solve the problem efficiently, even for very large inputs. Understanding and implementing memoization is a crucial skill for any engineer aiming to write performant and scalable software.