What is Recursion?

Simply put, it’s a function which calls itself. It’s great for tasks which are made up of sub-tasks, like working with nested objects.

Recursion has two elements to it: a recursive case which is calling the function again and running it, and a base case which is a condition to stop the function from running. If we didn’t have a base case then the function would continue to run.

As an example:

counter = n => {
  if (n === 10) {
    return "done"
  }
  return counter(n + 1)
}

counter(0)

And that’s it! Recursion is conceptually quite simple. All you need to do is to: (1) Identify the base case (i.e. when does the recursion stop?) (2) Identify the recursive case, and (3) return the value of your base case and recursive case.

Pros and Cons of Recursion

You could spend your entire career as a developer without ever implementing recursion. Instead you can use iterations like loops, but that’s not always a great idea.

There are some pros and cons to recursion. One one hand, recursion helps keep your code DRY (Don’t Repeat Yourself) and helps with readability. On the other hand, it creates an extra memory footprint as it pushes more onto the call stack. If you’re working on an application where memory is at a premium then recursion may not be the best option. This is sometimes a constraint added to algorithm challenges in interviews to see if you can identify this and come up with an alternative solution.

It’s worth bearing in mind, however, that many languages (including Javascript) have something called Tail Call Optimization which allows you to use recursion without increasing the call stack. So there are way of writing recursion functions to be more memory efficient.

Recursion is a great tool for when you’re working with unfamiliar data structures. It’s really useful for traversal and tree data-structures.

When should I use Recursion?

So when should you use recursion over iteration? Generally, when it gets to complicated problems like traversing or searching through trees and graphs (e.g. breadth-first search and depth-first search), or in some instances of sorting - then recursion is preferred.

Whenever you’re using a tree or converting something into a tree then consider using recursion. Other areas in which recursion can be useful are: Merge Sort, Quick Sort, Tree Traversal, and Graph Traversal.

Conclusion

Recursion is a fundamental concept in algorithms and can allow you to write more readable code. It does have a few trade-offs, particularly around space complexity but there are ways to mitigate this.

Overall recursion is a great tool at your disposal as a software engineer and it is definitely something that you should be familiar with.