What makes a function recursive?
Before we get started, let’s be clear — a recursive function is a loop. Much like a
for loop or
while loop, all we’re trying to do is repeat some code until some condition is met.
A recursive function is a function that loops by calling itself. It (obviously) gets more complicated than that, but we can get started with recursion with this oversimplified explanation. Yeah, I know… a bit esoteric… so let’s take a look at an example 👉
Tada! This function is calling itself (creating a loop) in a very simple recursive pattern. Let’s say we call this function and pass 1 to it…
countToFive(1); — what do we expect? We will see the numbers 1, 2, 3, 4, 5 get logged to the console. At 5, the recursion is terminated by the
if statement on line 2 (i.e. the function will not get to make another recursive call because the
return statement on line 2 ends the function execution). Each time the function is called,
n is passed to it — the only difference is we increment
n before passing it to the function. Run this function in your head a few times until you understand exactly what happens on each line during each iteration of this recursive function. It should be (almost) as easy as counting to five!
How to read a recursive function
An easy strategy for reading a recursive function is to break it down into three elements that are commonly used in a basic recursive pattern. All recursive functions do not follow this pattern, but simple ones likely do.
The condition is going to control if we make another recursive call. Exactly like we would use a condition in a
for loop or
while loop, we need to check for a condition to make sure the recursion only executes a certain number of times. Without a condition, we would have an infinite loop. This is a totally subjective take, but I would guess infinite loops most often occur in recursive functions… so be sure to avoid any patterns where your recursion does not terminate. In our
countToFive() example, we check if
n is greater than or equal to 5 and terminate our recursive execution (i.e. loop) once that condition is truthy.
The condition can be written anywhere in the function but most commonly will be written first in the function body or immediately before the recursive call. I’ve seen more developers get tripped up when the condition is written first in the function body, so we’ll chat a little more about that in the “Recursion” section below.
This is what your function is doing. Pretty straightforward! Logic in a recursive function is likely operating on some values that are getting passed to the next (recursive) function call. In our
countToFive() example, the only logic is logging and incrementing
n . We’ll run through a more complex “real world” example below.
Recursion is simply calling the function again. We do this to loop over the logic until the condition is met. When reading the recursive call in our
countToFive() example, we have to understand that the execution will loop back to the top when we pass any number less than 5. I like to think of this as the execution “wrapping” to the beginning, where the function ultimately could terminate. So if we think about this function as one loop, we have to realize that the condition on line 2 will be run last. I’ve found this is the most confusing piece for developers, so I’ll reiterate:
The condition on line 2 will be the last line to run in each recursive function execution.
This is because if we pass any number less than 5, one execution of the function will actually execute the function at least twice: one full execution and then another partial execution until the condition, which is then evaluated and either allows the recursion (i.e. loop) to continue or terminates the function execution (i.e. ends the loop).
I’ve been asked by devs if we have to return the recursive call — in some cases it’s better to return it, in other cases it’s not — it all depends! If we did not return the recursive call in our
countToFive() example, we would have to reorder some of the lines of the function body to get the same result. Can you figure out what would need to be reordered?
Using recursive functions
Recursive functions are appropriate for any problem you need a loop to solve. They start to become a better option if you need to hold some sort of state or memo in your loop or if the items you’re iterating through are ambiguous. Here’s a solid recursive function I just wrote IRL to find if any values of a nested object are truthy primitives 👉
Whoa! A little more terse than our first example! But it has the same elements we discussed. Let’s refactor this function to replicate the pattern of our
That’s a little better! Now we can easily see the condition is on line 2. The logic is on line 4, when we create an array from the values of
obj. The recursion is on line 6. Obviously the one glaring difference is there are multiple recursive calls as we iterate over the array using
.some()… but its not as scary as it looks.
This function is simply searching an object for truthy primitive values and returning either
false if the object has truthy primitive values or not. The return value always comes from the condition on line 2, which further emphasizes our point that we’ll repeat again: the condition on line 2 will be the last line to run in each recursive function execution. Because objects can be nested (and we don’t know how many objects are nested inside the
obj parameter… hint: it’s ambiguous) a recursive function is a great pattern to solve this problem.
Yes, there is a recursive call made for each value in the
obj parameter. And yes, if that value is an object, there is a recursive call made for each value in the child object… and so on… which may sound more confusing than it is. Here are two example arguments that we could pass to our function that may help us understand the execution a bit better:
zeroPrimitives will return false;
onePrimitive will return true (because
'world' is a truthy primitive). Again, this algorithm is looking for truthy primitives, which obviously does not include falsy primitives. 🙃
What makes a function recursive?
A recursive function is a function that loops by calling itself.
How can we read (and reason about) a recursive function?
Identify common elements in a recursive function…
Why use a recursive function?
A recursive function is a good solution if…
- You need to loop over a parameter
- You need to hold state or a memo during iteration of your loop
- The items you’re iterating through are ambiguous
🚢 Have fun and ship it!