Asynchronous Recursion

Non-blocking recursive algorithms

Recursion is a great way of performing complex computations. The classic example is the factorial function. I’m tired of using factorial for examples, though, so I thought I would take another example that my friend Eric Elliott tweeted about not too long ago: the quicksort.

The problem with recursive functions is they are blocking operations. To briefly reference another common — if contrived — example, imagine trying to calculate Fibonacci to even just 50. This operation could take several minutes to complete. Your program would just be sitting on-hold waiting for Fibonacci to calculate when you could be running other operations while that takes place.

If only we could make recursive functions asynchronous

Well, I have good news for you — we can!

So, back to that quicksort. By using Promises, we can perform the recursion asynchronously. Sure, you could easily wrap the standard quicksort with a single Promise and wait for the result, but why stop there?

The async quicksort performs quite nicely. It took an array of somewhere between 24k and 48k items before it exceeded the stack limit (I didn’t test it extensively enough to give you an exact number).

With an array of 24k elements, the Promise resolved in approximately 3 seconds. An already sorted array only took about 1.5 seconds. Not bad!

I would love to see if anyone can improve the performance of the quicksort algorithm itself.

Async is the new recursion

To sum up, this pattern for asynchronously recursive functions could have some interesting applications. If you find some useful or interesting ways to use async recursion in your programs, let me know by dropping me a comment or tweet it to me @therealklanni — I’d love to see what you’re doing with this!

Kevin Lanni is an Instructor for the Front End Web Development courses at RockIt Bootcamp in Phoenix, AZ. He has developed software for companies like GoDaddy, mentored developers, and has done onsite training for small businesses. He specializes in everything from JavaScript and web application development to CICD and Git, and he now dedicates his time to teaching these things to those who have little-to-no experience to prepare them for a new career in Web Development.

“There’s nothing more rewarding than teaching software development” — Kevin Lanni