Use await to avoid Stack Overflows

In my last post I mentioned that I should revisit my posts [1] and [2] about avoiding stack overflows. Well' I've done so and I've realised that while the technique that I describe there (using a timeout to exit the current call and then enter the next "recursion") makes sense in a pre-async/await world, but we can use a much more simple approach based on async-await. This technique that I'm going to show now is valid both for tail and not tail recursions

First let's see the code. I can transform these recursive functions (that in node, that lacks of Tail Call Optimizations, would crash when used with a large number

function factorial(n) {
	//return (n !== 0) ? n * factorial(n - 1) : 1;
	if(n === 0 || n === 1){
		return 1;
	}
	else{
		return n * factorial(n-1);
	}
}

function tailFactorial(n, total = 1) {
	if (n === 0) {
		return total;
	}    
	else{
		// proper tail call
		return tailFactorial(n - 1, n * total);
	}
}

Into these, that will not overflow the stack, cause basically we are no longer recursivelly stacking new frames in the stack, the await keyword is sort of avoiding the recursion

async function factorialWithAwait(n) {
	if(n === 0 || n === 1){
		return 1;
	}
	else{
		await "nothing";
		return (n * await factorialWithAwait(n-1));
	}
}


async function tailFactorialWithAwait(n, total = 1, resFn){
	if (n === 0){
		return total;
	}
	else{
		//this await prevents the stack overflow as we are exiting the function before the recursive call!
		await "nothing";
		//if we comment the await above, we'll get the stack overflows, cause this await here is AFTER the recursive call, so we continue to stack them up!
		return await tailFactorialWithAwait(n-1, n * total);
	}
}

This works thanks to how the eventloop and the microtask queue work in JavaScript.

To put it more simply, when a promise is ready, its .then/catch/finally handlers are put into the queue; they are not executed yet. When the JavaScript engine becomes free from the current code, it takes a task from the queue and executes it.

That means that adding an "await 'nothing'" in our code will cause that when JavaScript comes across this await for an already resolved value, it will add the ".then part" (that is what comes after the await) to the microtask queue, and will exit the current function (so releasing the current stack frame). Then it will take the task from the microtask queue and execute it.

As usual I've uploaded the code to a gist