Dennis Hackethal’s Blog
My blog about philosophy, coding, and anything else that interests me.
Simple JavaScript Recursion without Stack Consumption
Some JavaScript runtimes have safe tail recursion, meaning you can do something like this:
let foo = () => {
foo();
}
without worrying about a stack overflow. The compiler or interpreter (depending on your environment) sees that this functions employs tail recursion and pops the current function invocation off the stack before recurring.
However, not all JS environments do this. If your recursion needs to be safe while also being platform agnostic, here’s a way to recur safely without any special sauce from the compiler/interpreter:
let foo = () => {
setTimeout(foo);
}
The ‘trick’ is to call setTimeout
, which returns immediately without invoking foo
. (In case you’re wondering, it returns an integer identifying the timeout in case you want to cancel it later but we don’t care about that here.) And because it returns immediately, and since it’s the last statement in foo
, foo
now returns before it is invoked again.
The reason this works is that setTimeout
uses JS’s event loop. It puts foo
on a queue that will not be dequeued until the stack is empty. Only then is foo
run again. In that regard this solution is different from utilizing built-in stack-safe tail recursion: foo
will not be invoked not just until it itself has finished running, but until everything that’s currently on the stack has finished running. Depending on how quickly you need to run foo
, you may prefer one solution over the other.
For a real-life use case, see this answer of mine to a Stack Overflow question.
What people are saying
By the way, and to be clear, thanks to the use of
setTimeout
it doesn’t matter if your ‘recursive’ call is a tail call. It could be called anywhere in the fn and it shouldn’t make a difference. Just know that the rest of your function runs first.Reply