Solving the Climbing Stairs Problem Using SQL Recursive CTE and Fibonacci Sequence

In the world of coding interviews, some problems remain timeless because they teach essential concepts. The climbing stairs problem is one of those classic challenges that test your understanding of recursion and dynamic programming. What makes it interesting is you can solve it in different languages, and today we're focusing on how to implement it in SQL using a recursive common table expression (CTE).

If you’ve ever wondered how to find the number of distinct ways to reach the top of a staircase when you can climb either one or two steps at a time, this post will guide you through the process. You’ll also see how this problem connects to the famous Fibonacci sequence and how to translate this mathematical logic into a SQL query.

Understanding the Climbing Stairs Problem

Imagine a staircase that has n steps. Your goal is to get to the top, but with a catch: each move you make can only be either one step or two steps. The question is: how many distinct ways can you reach the top?

This might sound simple at first, but the number of ways grows quickly as the number of steps increases.

The problem is often used in coding interviews (on platforms like Leetcode) because it helps interviewers test the candidate’s grasp of important programming principles such as:

Understanding recursion
Applying dynamic programming
Problem-solving with mathematical patterns

Breaking Down the Problem With Examples

Let's start with smaller numbers of steps to get a feel for the numbers involved:

1 step: There is only one way to climb it — take a single step.
2 steps: You can either take two single steps or jump two steps at once. That makes 2 ways in total.
3 steps: The possible ways are:
1. Take one step, then two steps
2. Take two steps, then one step
3. Take three single steps

There are 3 ways for 3 steps.

If you continue this pattern, you’ll start noticing that the number of ways to climb a given step is always the sum of the ways to climb the two previous steps. This rule can be written as:

ways(n) = ways(n - 1) + ways(n - 2)

This pattern happens to match the well-known Fibonacci sequence, which makes it easier to compute the total number of ways for any number of steps efficiently.

Solving the Problem Using SQL Recursive Common Table Expressions (CTE)

SQL is often not the first language that comes to mind when solving algorithmic problems, but recursive CTEs provide a way to handle recursion within SQL queries. This fits well for problems like climbing stairs because you can express the Fibonacci number generation as a recursive query.

What Is a Recursive CTE?

A recursive CTE is a query construct in SQL that references itself, which enables performing operations like recursion and iteration inside a standard query. It consists of two main parts:

Anchor member: The base case that initiates the recursion
Recursive member: The part that calls itself until a termination condition is met

Defining the Recursive CTE for the Climbing Stairs Problem

We’ll name our CTE Fibonacci because the sequence of ways corresponds directly to Fibonacci numbers.

The CTE will use three arguments:

n: current step number
ways: number of ways to reach the nth step
previous_ways: number of ways to reach the previous step (n-1)

Initializing the Base Case (Anchor Row)

The starting point is for one step:

When n = 1, the ways to climb is 1.
For easier calculation, we initially set previous_ways also to 1, even though there’s no 0th step, to help compute the 2nd step.

The anchor row in SQL looks like this:

SELECT 1 AS n, 1 AS ways, 1 AS previous_ways

Building the Recursive Step

The recursive step calculates the number of ways for the next step (n + 1) based on the sum of ways to reach the current and previous steps. The SQL logic:

Increase the step number by 1 (n + 1)
Calculate the current ways as ways + previous_ways
Assign the current ways to previous_ways for the next iteration

Here's an example of the recursive select statement:

SELECT
  n + 1,
  ways + previous_ways,
  ways
FROM Fibonacci
WHERE n < @stairs

The recursion stops when the number of steps reaches the target value, which is stored in the variable @stairs.

Combining Anchor and Recursive Queries

You connect the anchor and recursive queries with UNION ALL to allow the recursion to unfold:

WITH RECURSIVE Fibonacci (n, ways, previous_ways) AS (
  SELECT 1, 1, 1
  UNION ALL
  SELECT
    n + 1,
    ways + previous_ways,
    ways
  FROM Fibonacci
  WHERE n < @stairs
)
SELECT * FROM Fibonacci;

Sample Output

n (step)	ways (number of ways to climb)	previous_ways
1	1	1
2	2	1
3	3	2
4	5	3
5	8	5

This table shows the growing number of ways to climb stairs for each step until reaching the target.

Why This Solution Matters and Where to Go Next

Learning how to solve algorithm problems using SQL is a powerful skill, especially for those aiming for data engineering or analytics roles with SQL-heavy workflows.

Understanding recursive CTEs strengthens your ability to work with complex SQL queries.
Combining recursion with dynamic programming teaches efficient problem-solving thinking.
This problem adds a valuable example to your SQL toolkit, useful for interview discussions or real-world database tasks involving sequences or hierarchical data.

If you want to sharpen your SQL skills further, consider booking a personalized SQL Mock Interview Session for hands-on practice and feedback.

For developers working remotely or setting up a home office, having the right equipment can improve productivity. Learn at Knowstar provides a detailed list of must-have tech gear for programmers to consider.

Also, boosting your analytics skills with certifications can open new career opportunities. Check out the Google Data Analytics Professional Certificate and the advanced version Google Advanced Data Analytics Professional Certificate.

About Learn at Knowstar and Staying Connected

Learn at Knowstar offers clear tutorials and guides to improve your SQL and programming skills. To stay updated and access more learning resources, follow these channels:

Whether you're preparing for interviews or expanding your programming knowledge, these resources can guide you forward.

The climbing stairs problem showcases how programming and math can work together, even in SQL. By mastering recursive CTEs and understanding the Fibonacci connection, you gain a skill that’s useful beyond just interviews. Try experimenting with the query and see how you can extend it to other scenarios involving recursion in SQL.