Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 63

Brute-Force Recursion for Climbing Stairs

Recommended resources

Introduction

Welcome back! In our previous lesson, we laid the theoretical groundwork for Dynamic Programming (DP). You learned how to spot problems that are good candidates for DP by looking for two key ingredients: optimal substructure and overlapping subproblems.

Today, we move from theory to practice. Our goal is to take a classic problem that exhibits these properties and formulate a brute-force recursive solution. This is the essential first step in the DP process. We need to define a correct, albeit inefficient, recursive structure before we can optimize it.

The problem we'll tackle is called "Climbing Stairs," a favorite in technical interviews. By the end of this lesson, you'll be able to translate its logic into a recursive function, which will be the foundation for our optimizations in the next lesson.

Understanding the "Climbing Stairs" Problem

Let's start by making sure we understand the problem statement.

The Problem: You are climbing a staircase that has n steps. You can climb either 1 or 2 steps at a time. In how many distinct ways can you reach the top?

For example, if n = 3, there are three ways:

  1. 1 step + 1 step + 1 step
  2. 1 step + 2 steps
  3. 2 steps + 1 step

The following video gives a clear and concise introduction to this problem.

Amazon Coding Interview Question - Recursive Staircase Problem

Watch this short clip from the CS Dojo channel. It explains the problem statement and works through an example for n=2.

Watch the first 1 minute and 21 seconds of the video to get a clear picture of the goal.

Devising a Recursive Strategy

As we discussed in the last lesson, problems that ask "how many ways...?" and involve a sequence of choices are often solvable with recursion. Our task is to break the problem of climbing n stairs into smaller, similar subproblems.

The Core Insight: The Final Step

Think about how you could arrive at the very last step, the n-th stair. Your final move must have been one of two possibilities:

  1. You took a single step from stair n-1.
  2. You took a double step from stair n-2.

There are no other ways to land exactly on stair n. This insight is the key to our recursive solution. The total number of ways to reach stair n is simply the sum of the ways to reach stair n-1 (and then take one step) and the ways to reach stair n-2 (and then take two steps).

This gives us a recurrence relation:

Does this look familiar? It's the same structure as the Fibonacci sequence!

The next video provides a fantastic visual walkthrough of how to arrive at this conclusion by analyzing small cases and identifying the pattern.

Amazon Coding Interview Question - Recursive Staircase Problem

Let's continue with the CS Dojo video. The presenter does an excellent job of breaking down the problem to derive the recurrence relation.

Watch from 02:13 to 08:36. Pay close attention to how working through examples for n=1, 2, and 3 helps reveal the underlying pattern. The idea of relabeling the stairs from the top down is a clever way to see the subproblems more clearly.

A General Method for Finding Recurrence Relations

The intuitive process from the video is great for this problem. As you face more complex problems, it can be helpful to have a more structured approach. The take U forward channel suggests a three-step "trick" for formulating recurrence relations.

DP 2. Climbing Stairs | Learn How to Write 1D Recurrence Relations

This video from the 'take U forward' channel offers a general framework for creating recurrence relations for 1D DP problems. This is a powerful mental model to add to your toolkit.

Watch from 01:32 to 06:12. Focus on the three key steps outlined for writing any recurrence relation. This gives you a repeatable strategy for future problems.

Let's apply that 3-step strategy to our problem:

  1. Represent the problem in terms of an index: Let's define a function f(i) that returns the number of ways to reach stair i. Our goal is to find f(n).
  2. Do all possible things on that index: To reach index i, we could have jumped from i-1 or i-2. So the subproblems we need to solve are f(i-1) and f(i-2).
  3. Sum up the results (for "count ways"): Since we want the total number of ways, we sum the results of the subproblems: f(i) = f(i-1) + f(i-2).

As you can see, this structured method leads to the exact same recurrence relation.

Establishing the Base Cases

A recursive function needs one or more base cases to stop the recursion. What are the simplest possible inputs for our ways(n) function?

  • ways(1): How many ways are there to climb 1 stair? Just one: a single 1-step jump. So, ways(1) = 1.
  • ways(0): This is a bit more abstract. How many ways are there to climb 0 stairs? The standard convention in these problems is to say there is one way: do nothing. You are already at the "top" of a 0-stair staircase. So, ways(0) = 1.

These two cases, n=0 and n=1, are our base cases. They don't depend on any smaller subproblems and can be returned directly.

Putting It All Together: The Brute-Force Code

Now we have all the pieces to write our recursive function: the recurrence relation for the general case and the return values for the base cases.

Let's look at a complete implementation.

Climbing Stairs | Leetcode 70 | Solution 1: Brute Force Approach

This article from the blog 'Code and Debug' provides a clean implementation of the brute-force solution. It clearly lays out the intuition, code, and a step-by-step trace.

Read the section 'Solution 1: Brute Force Approach (Pure Recursion)'. Study the Python code and then carefully follow the 'Dry Run' for n=4. This will help you visualize how the recursive calls unfold.

The dry run in the article shows something important: func(2) is calculated multiple times. This is the overlapping subproblems property we discussed in the last lesson, made tangible.

Let's visualize this with a recursion tree for n=5.

Recursion Tree for N=5 (Climbing Stairs Problem)
This diagram shows the recursive calls for finding the ways to climb 5 stairs. Notice how the same subproblems, like `f(3)` and `f(2)`, are computed repeatedly in different branches of the tree. This redundancy is what makes the brute-force approach inefficient.

This inefficiency is exactly what we will fix with Dynamic Programming. But having this correct brute-force model is the critical starting point.

Conclusion

In this lesson, you successfully took a problem description and transformed it into a working, albeit inefficient, recursive algorithm. This process is the first and most important step in solving any DP problem.

Key Takeaways:

  • The "Climbing Stairs" problem can be solved by finding a recurrence relation.
  • The key insight is that to reach stair n, you must have come from either stair n-1 or n-2. This leads to the relation: ways(n) = ways(n-1) + ways(n-2).
  • A complete recursive solution requires both the recurrence relation for the recursive step and clearly defined base cases (ways(0)=1, ways(1)=1) to terminate the recursion.
  • The resulting brute-force solution is inefficient because it repeatedly calculates the same subproblems, leading to an exponential number of calls.

Preview of the Next Lesson:

We've now formulated a brute-force solution and clearly seen its inefficiency due to overlapping subproblems. In the next lesson, we will optimize this exact function. You will learn your first DP technique, memoization, which eliminates redundant calculations by storing the results of subproblems. We will see how a small change to our code can dramatically improve its performance.