Dennis Hackethal’s Blog

My blog about philosophy, coding, and anything else that interests me.

Simple JavaScript Recursion without Stack Consumption

Published · 1-minute read

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.

#82 · dennis (verified commenter) ·
Reply

What are your thoughts?

You are responding to comment #. Clear

Preview

Markdown supported. cmd + enter to comment. Your comment will appear upon approval. You are responsible for what you write. Terms, privacy policy
This small puzzle helps protect the blog against automated spam.

Preview