Recursion

When I first was introduced to the topic of Recursion in Javascript my first reaction was confusion. It was very hard to wrap my head around how a function could call itself from within itself, and why this would be a valuable thing to do. After doing some more research I found out how powerful Recursion can be to solve complex problems such as iterative branching, or traversing the nodes of complex, or non-linear data structures. At the same time I found out that this power comes at a cost, and exerting this power just because you can isn’t always the best solution. Let’s do an overview, and start with the definition.

Recursion: An act of a function calling itself. Recursion is used to solve problems that contain smaller sub-problems. A recursive function can receive two inputs: a base case (ends recursion) or a recursive case (continues recursion). MDN

This definition seems simple enough, and as always MDN has done a great job to make it clear. When I first tried to apply this to an example it led to a bit more confusion, but after several examples I was able to begin connecting the dots. The countdown example used by several blogs did a great job to help me wrap my head around this concept. We will go through two versions of the countdown example below, one that will produce an error so we can further understand what is going on when we use Recursion, and then the right version so we can see Recursion in action.

The Countdown Example, with an error

let countdown = (n) => {
console.log(n)
countdown(n - 1)
}
countdown(10)

Here we have defined a variable named countdown to equal a function that takes one argument “n” which is an integer. Countdown will console log “n” and then proceed to call it self again with “n” minus 1. Once it calls it self again it returns back to the top and continues the process. This seems simple enough, but something is wrong here and it becomes evident when we call the function and receive the following error:

-17569
-17570
RangeError: Maximum call stack size exceeded

The numbers above the error tell us that Javascript does its best to carry out our instructions, however it breaks after about -17,570 and realizes that it does not have the memory to keep track of all the times it’s calling the countdown function. This error is typically referred to as ‘Stack OverFlow’. A programs stack is the available memory it has to do operations, and the more demanding the action is, the more demanding it is on the stack. Since our above example led to a infinite countdown we ran out of memory at about -17,570. When we use Recursion, Javascript is using the stack to keep track of each iteration of that Function, where it was called, and it’s variables. With our basic example there is not to much to keep track off, but with more complex examples one can run out of memory even faster than the example above.

Like the infinite loop Error?… NO! They are not the same error!!!

This may sound like a familiar error that we have seen in the past when we fall into an infinite loop. It is important to point out however that they are not the same thing! The infinite loop error is an error that comes from the recognition that you will never break out of the loop given the parameters. The infinite loop error is not triggered because of a lack of memory, but the Recursion error is. This is an important distinction.

The countdown example, without an error

Going back to the example, in order to to be able to use Recursion we must also have some logic letting our function know when it is time to stop calling it self. We can re-write the above example in the following way:

let countdown = (n) => {
console.log(n)
if(n === 0){
console.log("Countdown Complete!")
} else {
countdown(n - 1)
}
}

Now our function would know when to stop calling it self and we would get the following result:

10
9
8
7
6
5
4
3
2
1
0
Countdown Complete!
=> undefined

At this point we can draw some parallels between Looping and Recursion. Both of these methods are designed to help us to repetitive tasks. Both of them will provide us with errors if something goes wrong. Although the errors may come about because of similar situations, again it is important to note that they are being generated for different reasons.

So why would we use Recursion over a Loop?

After doing some more research I found that three important factors to consider are performance, readability, and compatibility with the language. Their may be other factors to consider depending on the use case, but these three factors will always be something you want to keep in mind when considering Recursion.

Performance:

Recursion is an activity that requires a lot of memory, and is referred to as costly because of this. If you are making a decision to implement a function that uses Recursion instead of a loop, keeping this cost in mind will be important. Additionally, all Recursive functions can be written iteratively so making things more efficient should always be an option. This may lead to very long unreadable code, but it will be more efficient when it comes to memory. Like most things in life it is about balancing the trade offs, and making the best decision based on what you are trying to accomplish.

Readability:

Although Recursion is a very costly activity in regards to memory, it can make things very readable and more elegant. This is especially important in the development phases when many engineers may be working together to find solutions. Keeping the code readable makes it easier for engineers to stay on the same page, and Recursion will usually be a lot less code as well. Once everything is hashed out, the code can be refactored by trying to implement an iterative approach to improve performance. Because of it’s readability Recursion is often used in academics to solve complex math problems.

Compatibility with the Language:

Another caveat with Recursion is that some languages are better equipped to handle the memory burden that comes with using it. Since ECMA script 6 Javascript has a feature called “Tail Optimization” which recognizes Recursive functions and provides them some logic so they are not unnecessarily using up more memory than they need to. Other languages also have similar capabilities and may be equipped to handle recursion.

For languages that are not equipped to handle Recursions, Trampoline Functions can be used as a workaround. A Trampoline Function is a way to force Javascript to use Recursion and not use up all the memory in the stack by using binding. The problem with using trampoline functions is that it takes away from the elegance and readability of using Recursion in the first place. So they are typically used with discretion. Trampoline functions are a big topic on their own, and I am brushing over them here, but if you are interested in finding out more check out the Resources section below!

Summary:

Using Recursion is a powerful way solve problems and it can be a fantastic way to get your thoughts out on the screen. Keeping track of what you are trying to accomplish and how it will potentially be used will help you determine if using Recursion would be appropriate. Hope you found this blog about Recursion helpful! Check out the resources below for some phenomenal information in regards to the topics we covered. The Authors below did a great job of brining me up to baseline when it comes to this topics. They explained things very clearly and had some great examples! Without them I could have not written this blog post, so many thanks for the wisdom!

Resources:

FunFunFunctions, Recursion Video

M. David Green, Recursion Blog

Stack Overflow , Wikipedia Stack Overflow definition

Ragan Wald, Trampoline Functions, Trampoline Function Blog

Like what you read? Give Pradeep Dayaram a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.