Recursion Can Be Weirder Than You Think

I love recursion. I think it's a very elegant way of writing code, and sometimes it lets you write simple but yet effective pieces of code. And if you happen to use languages like Scala, then recursion is a must.

But when I was thinking I was proficient in the use of recursion, I ran into a book called "Mastering JavaScript Functional Programming" by Federico Kereki, and in the section on using recursion, he gave a recipe that went like this:

1) Assume you already have an appropriate function to solve your problem.
2) Then, see how the big problem can be solved by solving one (or more) smaller problems.
3) Solve those problems by using the imagined function from step 1.
4) Decide what are your base cases, simple enough that they be (sic) solved directly, not requiring any more calls.

When I read this, mainly the first point, I was amazed by the concept: To solve your problem recursively, start by assuming you already solved the problem! A recursive recipe for a recursive solution!

Although after creating a fair share of recursive functions in my life this statement sounded intuitively reasonable, I felt I had to test it in practice. The opportunity came a couple days after when I was solving the "Climbing Stairs" problem at LeetCode. The problem statement was simple enough:

You are climbing a stair case (sic). It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

So, using the recipe you could do something like this:

1) Assume you already have an appropriate function to solve your problem.

Simple enough! I'll assume I already have an appropriate function using this JavaScript code:

function climbStairs(n) {
};

That was easy! Now, for the second step:

2) Then, see how the big problem can be solved by solving one (or more) smaller problems.

According to the statement, you can either climb one or two steps. So, if I assume this function already can calculate the number of ways I can climb to the top, the answer will be the number of ways I can climb after one step (n - 1) plus the number of ways I can climb after two steps (n - 2).

Now, for the third part:

3) Solve those problems by using the imagined function from step 1.

This just means translating that statement to code, so you end with this:

function climbStairs(n) {
  return climbStairs(n - 1) + climbStairs(n - 2)
};

That is the number of ways I can climb by one step plus the number of ways I can climb by two steps. Looks reasonable, but still not sure how this works. Let's just do the fourth and final step:

4) Decide what are your base cases, simple enough that they be solved directly, not requiring any more calls.

For this problem I could distinguish three base cases:

The first case is when you have zero steps, in which case there's no stair to climb, so zero ways to climb it.
The second, when your stair has only one step, there's only one way to climb: 1 step.
The third, when your stair has two steps, there are two ways to climb: The first being 1 step + 1 step; the second by two steps.

function climbStairs(n) {
  if (n === 0) return 0
  if (n === 1) return 1
  if (n === 2) return 2
  
  return climbStairs(n - 1) + climbStairs(n - 2)
};

Of course, in this case, you could simplify by replacing the three if's with:

if (n <= 2) return n

But for the sake of the method, let's leave the three explicit conditions.

And that's it! At least for this problem, the four recipe steps are pretty straightforward. So, after following them I was greatly surprised when the simpler test cases passed without a problem (for a large number of steps there were timeout problems that I solved using memoization, but that's material for another article).

But to be honest, my biggest surprise was that I was able to solve the problem and I didn't know how I did it! I knew it worked because it passed the test cases, but my head hadn't figured out how or why it worked!

After solving this problem I tried the recipe in a couple more problems and it always worked nicely, but I still have this subtle feeling of awe. Now I not only think recursion is an elegant and effective technique of programming, but it's also kind of magic...

God, I love recursion! ;-)