Categories

Asynchronous Recursion with Callbacks, Promises and Async.

Creating asynchronous functions that are recursive can be a bit of a challenge. This blog post takes a look at various different approaches, including callbacks and promises, and ultimately demonstrates how async functions result in a much simpler and cleaner solution.

A simple example

Recently I was writing some code, for a GitHub bot, which needed to obtain some data from a API endpoint that provided a paged output. My bot needed to obtain approximately 1000 records, which in this case required up to 10 asynchronous operations to obtain the full dataset. I explored various different approaches to this problem, which I’ll outline in this blog post.

Rather than use an external API, for the purposes of this blog post I’ll be using a contrived example that illustrates the same problem:

NOTE: The above code uses default parameters, arrow functions and the spread operator. I’ve been running these snippets within Chrome that has full support for these language features. For other execution environments, you might need to transpile.

All of the examples in this post look at the same simple problem; how to create a getSentence function that retrieves the entire sentence?

The next two sections cover a simple iterative and recursive approaches, without any asynchrony. If you’re comfortable with recursion, you might want to skip these!

An iterative approach

The following function uses an iterative approach to obtain the complete sentence.

There isn’t really much to say about this approach, it repeatedly invokes the getSentenceFragment function, accumulating the result into the aggregateData variable. It also keeps track of the current offset. When the fragment.nextPage property is undefined, the loop exits and the function returns. Simple.

This version of the code is structurally much simpler, without the need for any variables to maintain the current iteration state. With a recursive function, this same information is stored in the stack.

With the Chrome debugging tools, by breaking on the termination condition you can see four invocations of this function. You can also navigate up and down the stack to see the fragment and offset values that are within scope on each invocation:

When the termination condition is reached each function returns, unwinding the stack, to create the returned value at the original point of invocation.

Now let’s have a look at what happens when we introduce some asynchrony.

Asynchronous recursion with callbacks

The first approach we’ll look at is a little old-fashioned, using callback functions. The first step is to change the getSentenceFragment function so that it returns its result asynchronously.

Using a simple setTimeout, we can update the getSentenceFragment as follows:

And now for the other branch, where there is another page to fetch, which is where the function is invoked recursively. Here we invoke getSentence, however, it returns asynchronously, so we need another callback, where the concatenation takes place..

Now with the synchronous version of the recursive code, you could see the recursive invocations within the call stack (by placing a breakpoint at the termination condition). With the asynchronous version you can actually do the same:

Although you cannot view the scope of previous invocations (which would require a form of time-travel!).

The recursive version of the getSentence function that uses callbacks is not very easy to follow, with the nested callback introducing more functions and scopes.

Let’s see how a promise-based implementation compares …

Asynchronous recursion with promises

Once again, the first step is to update the getSentenceFragment function:

If a non promise value is returned by a then handler, it is converted to a promise, as per Promise.resolve(value).

Getting back to our getSentence implementation, the getSentenceFragment invocation returns a value to its then handler. The value returned by this function is itself a promise that is the return value of getSentence. The value returned is denoted by ..., so let’s fill them in.

Adding both the termination condition and the recursive step in one go …

Much the same as with the callback implementation, you can breakpoint the termination condition and see the async call stack.

Comparing the promise version of this function to the callback implementation, the code is a little cleaner and easier to follow. However, it is still a lot more complex than its synchronous counterpart.

Asynchronous recursion with async / await

The purpose of async functions is to simplify the use of promises. As you’ve seen in the previous example, moving a very simple function from synchronous to asynchronous has a significant effect on code complexity, and with our recursive example, both callbacks and promises are quite messy.

Before diving into the recursive function, let’s take a look at converting the getSentenceFragment into an async function …

The getSentenceFragment async function pauses execution when it meets an await, waiting for the resolution of the returned promise, then resumes execution. Simple and elegant. This function now looks almost exactly the same as its synchronous counterpart.

Because async function return promises, the above code can be used with the promise version of our getSentence function.

Let’s look at the async equivalent of getSentence. Once against, well return to the original synchronous version:

I really like how this has come full-circle, with the async version looking almost exactly the same, and being just as understandable, as the original synchronous version.

I’ll definitely be making much more use of async functions. I am sure they will also help resolve a number of other common issues with promises that I have written about in the past, but that’s a topic for another day.

I am Technology Director at Scott Logic and am a prolific technical author, blogger and speaker on a range of technologies.

My blog includes posts on a wide range of topics, including HTML5 / JavaScript and data visualisation with D3 and d3fc. You'll also find a whole host of posts about previous technology interests including iOS, Swift, WPF and Silverlight.