A First Step Into Writing Recursive Functions
Learn to write functions that call themselves
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.
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.
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.
- 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.
- The call
factorial(2)is executed. Note, our
factorial(3)call is still waiting to be completed. Now,
factorial(1)must be evaluated.
- The call for
factorial(1)is executed. Both
factorial(2)are waiting to be completed. We recurse down into
- The call for
1 * 1where the second 1 is the return value of
2 * 1where 1 is the return of
3 * 2where 2 is the return of
Visualizing these steps with indentation helps make sense of everything.
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.
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!