A First Step Into Writing Recursive Functions

Recursion is one of those topics that causes blinking, head-scratching, and overall confusion. The idea of a function calling itself feels like you’re going down a rabbit hole, and the truth is, that’s a pretty accurate feeling for what your function is actually doing.

Even after understanding recursion for years, whenever a problem is solved recursively, I have to stop and take an extra minute to make sure I understand what I’m looking at.

But worry not, as we’re going to break down recursion and go through a real-world example.

I’ll be writing examples in both Python and JavaScript and by the end of this article, you’ll hopefully understand that the article’s title is actually a pun.

Parts of a Recursive Function

I’ve found that teaching recursion is easier through examples. The concept is just too abstract to visualize. So, let’s define a function to calculate the factorial of a number.

A number’s factorial value is that number times every positive integer below it. So, 3 factorial — written 3! — would be 3 * 2 * 1 which equals 6.

Python

JavaScript

Breaking down these examples, there are two main parts to a recursive function: a base case and a recursive case.

In our factorial function, we use an if/else statement to separate the two. Now, let’s walk through how this function actually executes, command-by-command.

1. The call factorial(3) is executed. Within that function, the value of 3 * factorial(2) is supposed to be returned. So, we need to execute factorial(2) to complete our return.
2. The call factorial(2) is executed. Note, our factorial(3) call is still waiting to be completed. Now, factorial(1) must be evaluated.
3. The call for factorial(1) is executed. Both factorial(3) and factorial(2) are waiting to be completed. We recurse down into factorial(0).
4. The call for factorial(0) returns 1.
5. Now, factorial(1) returns 1 * 1 where the second 1 is the return value of factorial(0).
6. Then, factorial(2) returns 2 * 1 where 1 is the return of factorial(1).
7. Finally, factorial(3) returns 3 * 2 where 2 is the return of factorial(2).

Visualizing these steps with indentation helps make sense of everything.factorial(3)
 factorial(2)
   factorial(1)
     factorial(0) => returns 1
   returns 1 * 1
 returns 2 * 1
returns 3 * 2

So, essentially, to evaluate our original function call factorial(3), we need to call the function over and over until the base case hits, breaking the recursive cycle and allowing all previous calls to evaluate in reverse order.

When Do I Use Recursion?

Now that we’ve gone through an example, we need a compelling reason to take the time and really commit this to memory and understanding.

Sometimes, recursion is necessary. I most commonly use recursion to manipulate complex data structures such as arrays, dictionaries, and lists.

For example, if I want to remove all null values from a dictionary/object and need to prepare for nested dictionaries/objects, then I would use a recursive function like these.

Python

JavaScript

Conclusion

It’s also important to understand the limitations of recursion. Recursive functions are very memory-intensive. Since each call waits on its subsequent recursive calls, the process stack can grow very tall very quickly.

Learn to implement recursive functions and identify use cases when they are appropriate. Not every problem that can be solved with recursion should be; however, you’ll be glad it’s an arrow in your quiver once you need it.

If you get the pun by now, then you’re well on your way!