A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

The Staircase Problem

We’ve now learned to use a new mental strategy for solving certain computational problems using top-down recursion. However, you may still be skeptical and ask, “Why do we need this new mental strategy anyway? I’ve been able to solve these problems with loops just fine until now.”

Indeed, you may not need a new mental strategy for simpler computations. However, when it comes to more complex functions, you may find that the recursive mindset makes the writing of code much easier. It certainly does for me!

Here’s one of my favorite examples. There’s a famous question—known as the “Staircase Problem”—that goes like this:

Let’s say we have a staircase of N steps, and a person has the ability to climb one, two, or three steps ...