Exploring Recursive Promises In JavaScript
Yesterday, in my post about adding retry logic to bulk updates in PouchDB, I made use of a recursive promise chain. Recursion is a difficult topic on its own; as are Promises; so, putting the two together is enough to make one's head hurt. As such, I thought it might be worthwhile to perform a quick exploration of what a recursive Promise is and how it works in JavaScript. But, be warned - I am not an expert with Promises; what I discuss here is simply a representation of my own personal mental model and how I use it to manage the complexity of Promises.
Run this demo in my JavaScript Demos project on GitHub.
Before we look at "recursion," I want to look at something that is not recursion. But, it's something that may feel like recursion because it happens in a loop. Namely, "reduction." One of the "Promise patterns" for running a number of asynchronous tasks in series (ie, one after the other) is to reduce those tasks into a single Promise chain. In this approach, each task is bound to the fulfillment of the previous task using the .then() function:
var promise = Promise.resolve()
.then( runTaskA )
.then( runTaskB )
.then( runTaskC )
;
Here, we've hard-coded the series of .then() bindings. But, this could be rewritten to "reduce" the collection of tasks into a single promise:
var promise = [ runTaskA, runTaskB, runTaskC ].reduce(
function( series, task ) {
return( series.then( task ) );
},
Promise.resolve()
);
This is the same code. The only difference is that we're using a reducer to bind the execution of one task to the fulfillment of the previous task (using .then()).
To see a slightly more concrete example, let's reduce a collection of numbers into an asynchronously calculated sum:
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<title>
Exploring Recursive Promises In JavaScript
</title>
</head>
<body>
<h1>
Exploring Recursive Promises In JavaScript
</h1>
<h2>
Using Reduce, Not Recursion
</h2>
<p>
<em>Look at console — things being logged, yo!</em>
</p>
<script type="text/javascript" src="../../vendor/core-js/2.4.1/shim.min.js"></script>
<script type="text/javascript">
var values = [ 1, 2, 3 ];
// Here, we are going to reduce the Values collection down into an asynchronous
// SUM calculation in which each link in the Promise chain will add one value to
// the running sum and then return the running sum to the next promise link.
var promise = values.reduce(
function reducer( promiseChain, value ) {
// In each iteration of the reducer, we have a PromiseChain that will
// resolve with running aggregate (starting with the initial value of 0).
// To get at that sum, we have to bind to the resolution of the chain,
// thereby adding a new link to the end.
var nextLinkInChain = promiseChain.then(
function( previousValue ) {
return( previousValue + value );
}
);
// Return the "next link", which is currently the "last link" in the
// Promise chain.
return( nextLinkInChain );
},
Promise.resolve( 0 ) // Start the promise chain.
);
// This looks and feels a bit like recursion, but it's not. We're just using an
// iterator to translate a series of values into a series of .then() bindings.
// But, this could just as easily have been HARD-CODED to look something like:
// --
// Promise.resolve( 0 )
// .then( function( sum ) { return( sum + 1 ); } )
// .then( function( sum ) { return( sum + 2 ); } )
// .then( function( sum ) { return( sum + 3 ); } )
//
// Read more: // https://github.com/kriskowal/q#sequences
// --
// In either case, the reduced Promise will now resolve to the sum of the values:
promise.then(
function( sum ) {
console.log( "Sum of values:", sum );
}
);
</script>
</body>
</html>
Here, each link in the Promise chain resolves with the running total. Which means that each link in the Promise chain receives the running total from the previous step's resolution. It then adds its own value and returns a new promise. Running this, we can see that it sums the values:
Sum of values: 6
Using Reduction with Promises is a powerful pattern that allows you to run asynchronous tasks in serial. But it's not recursion. Reduction builds a single, linear Promise chain - recursion builds branching Promise chains. This is a small but fundamental difference that may be hard to spot at first.
To explore this difference, let's create a recursive Promise chain that simply counts down from 3-to-0. In the following demo, I have a pre and post function surrounding a Promise chain link that recursively calls itself:
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<title>
Exploring Recursive Promises In JavaScript
</title>
</head>
<body>
<h1>
Exploring Recursive Promises In JavaScript
</h1>
<h2>
Recursion With Internal Function
</h2>
<p>
<em>Look at console — things being logged, yo!</em>
</p>
<script type="text/javascript" src="../../vendor/core-js/2.4.1/shim.min.js"></script>
<script type="text/javascript">
Promise.resolve()
.then(
function() {
console.group( "Recursion - inline function." );
return( 3 );
}
)
// In this link of the promise chain, the resolution function is explicitly
// named. This way, the function reference can be invoked from within its
// own function body.
.then(
function recursiveFunction( n ) {
console.log( "Entering recursive function for [", n, "]." );
// Once we hit zero, bail out of the recursion. The key to recursion
// is that it stops at some point, and the callstack can be "rolled"
// back up.
if ( n === 0 ) {
return( 0 );
}
// Internally to this promise link, we're going to start a NEW
// PROMISE CHAIN whose fulfillment will become the continuation of
// the parent promise chain. This fundamentally different from the
// reduce() example.
var promise = Promise.resolve().then(
function() {
return( recursiveFunction( n - 1 ) ); // RECURSE!
}
);
return( promise );
// NOTE: To be ultra-concise, I could have written the following;
// but, I think that would have made the example harder to follow.
// --
// return( Promise.resolve( recursiveFunction( n - 1 ) ) );
}
)
.then(
function() {
console.groupEnd();
}
)
;
</script>
</body>
</html>
If you look at the recursiveFunction() body, you can see that it creates a new promise by binding to the .then() method and then recursively calling itself with (n-1). This looks a bit like the reduction example in that each execution of the function is creating and returning a new promise. But, the fundamental difference is that the reduction example builds on the passed-in promise chain whereas this recursive example starts a completely new promise chain.
When thinking about a Promise chain as "links" of functionality, it might help to visualize the difference like this:
In the preceding example, it can be hard to build this mental model because I'm using a core feature of JavaScript which exposes named function references to their own execution context. Using this approach makes it feel like the recursion is happening "inline" with the Promise chain. But, if we refactor this code, to pull the recursive calls out into a separate function, the structural difference may become more obvious:
<!doctype html>
<html>
<head>
<meta charset="utf-8" />
<title>
Exploring Recursive Promises In JavaScript
</title>
</head>
<body>
<h1>
Exploring Recursive Promises In JavaScript
</h1>
<h2>
Recursion With External Function
</h2>
<p>
<em>Look at console — things being logged, yo!</em>
</p>
<script type="text/javascript" src="../../vendor/core-js/2.4.1/shim.min.js"></script>
<script type="text/javascript">
Promise.resolve()
.then(
function() {
console.group( "Recursion - external function." );
return( 3 );
}
)
.then(
function( n ) {
// With the recursive function factored out into its own stand-alone
// function, it's a lot easier to see that we are creating a totally
// TANGENTIAL BRANCH of the Promise chain.
// --
// A
// |
// B --> B'3 --> B'2 --> B'1 --> B'0
// |
// C
var tangentialPromiseBranch = recurseToZero( n );
return( tangentialPromiseBranch );
}
)
.then(
function() {
console.groupEnd();
}
)
;
// I am the recursive function, factored-out into its own function.
function recurseToZero( n ) {
console.log( "Entering recursive function for [", n, "]." );
// Once we hit zero, bail out of the recursion. The key to recursion is that
// it stops at some point, and the callstack can be "rolled" back up.
if ( n === 0 ) {
return( 0 );
}
// Start a NEW PROMISE CHAIN that will become the continuation of the parent
// promise chain. This new promise chain now becomes a completely tangential
// branch to the parent promise chain.
var tangentialPromiseBranch = Promise.resolve().then(
function() {
return( recurseToZero( n - 1 ) ); // RECURSE!
}
);
return( tangentialPromiseBranch );
}
</script>
</body>
</html>
In this version, I think it becomes more clear that the recursion is not a continuation of the parent promise chain. Instead, it is a completely new, tangential Promise chain, whose fulfillment continues on to the next link in the parent Promise chain. Of course, tangential or not, this all still executes in serial, which is how we get the .group() and .groupEnd() calls to wrap around the recursion branch:
Hopefully this has added some clarity and not just left you more confused. Promises, on their own can be really hard to understand. And the concept of branching a Promise chain is somewhat arbitrary; meaning, it's nothing more than a personal mental model that helps me think about Promises. Asynchronous actions performed inside of a Promise chain are just branches off of that Promise chain. And, recursion is just one of the ways you can build one of those branches.
Want to use code from this post? Check out the license.
Reader Comments
Thanks for the article. I was thinking about this the other day and was wondering if you know of a way to have something equivalent to tail call optimization. One problem that you get with recursive promises is that ot keeps the whole chain of promises in memory and I can't think of an easy way to get rid of them while only keeping the latest churned value.
Any ideas?
@Marc,
That's a really interesting question. To be clear, I know "of" tail-call optimization, but I am not so familiar with the details of how it works. From what I understand, it's a way for the Compiler to turn recursion into a for-loop when the recursive call is the last call in the original "block".
I wonder if there is a way to leverage the "yield" concept in Generators to loop over Promises instead of chaining them together in such a way that it only holds on to the last one in memory. I've played around a bit with Generators, to get familiar with the mechanics, but don't yet have the best mental model.
Hmmm, I'll have to noodle on that. Could be a fun thing to experiment with if I can see memory allocation in the Chrome Profiler.
Awesome read, thank you for taking the time to explore this!
I started thinking about how something like this would work with the FileReader API and got stuck towards the end of the chain where you return (previousValue + value).
How would I go about changing that if, let's say, I wanted to do something like reader.onload? How would I make it wait before going to the next chain?
I have a stack question open as well, in case you wanted to see some code:
https://stackoverflow.com/questions/45760885/how-to-load-large-batch-of-files-with-filereader-api-without-locking-up-the-brow
Thanks again for the article, really great stuff!
Actually, I think I figured out where I was going wrong but my solve feels a bit like recursion though. Check out that stack post above for more details.
Thanks again!
Nicely broken down. Noob question; Is recurseToZero subject to a the old "running out of heap/stack space" errors that we see in traditional recursive functions? That is, if it's used to process a large array (over 1k of iterations) will it eat up memory or does the promise in recurseToZero [that] "...then does another recurseToZero" work more like an event emitter... just taking on tasks to be done sequentially?