JS - Microtask Recursion Trick

Recursion is an operation that a lot of developers are trying to avoid since it is very dangerous, and can break the execution of applications in a fraction of a bug, but it is needed in some scenarios (e.g tree iteration). This post is for technical readers who want to learn how to use recursion efficiently using Microtasks. I assume that you're already familiar with JavaScript event loop mechanism

So, my story is not too long and started on the last weekend when I needed to write code to traverses a tree object.

I needed to create a code with a recursive logic, so I needed to split my code to avoid stack overflows (RangeError exceptions) since the stack is limited to maximum stack frames.
You can check your browser stack limitation here

Naturally, I knew that I need to "break" the iteration using timing API (setTimeout/setInterval) and I started with a naive approach that is similar to this structure:

function run() {
    const max = 50000;
    let count = 0;

    const start = performance.now();
    (function run() {
        if (count < max) {
            count++;
            if (count % 100 === 0) {
                setTimeout(run, 0);
            } else {
                run();
            }
        } else {
            console.log(`Done: ${performance.now() - start}`);
        }
    })();
}

When I checked the execution time of this given code I wasn't too happy ( ~2500ms ) and I wanted to get better results.
I was thinking about a better approach to my problem, I came up with a new pattern. I replaced the usage of Timing API with microtasks.

function run() {
    const max = 50000;
    let count = 0;
    const start = performance.now();

    return new Promise((resolve) => {
        (function _run() {
            if (count < max) {
                count++;
                if (count % 100 === 0) {
                    queueMicrotask(_run);
                } else {
                    _run();
                }
            } else {        
                console.log(`Done: ${performance.now() - start}`);
                resolve(performance.now() - start);
            }
        })();
    });
}

The execution time of this pattern was 675.6 times faster! ( 3.7ms)

Microtask usage approach is working better rin such scenarios for two main reasons:

1. Timing API is not deterministic

   • browsers are using throttling on repetitive timing API calls (official minimal timeout time is 4ms )
     • Timing API:
       • setTimeout
       • setInterval
     • Micro task examples (no throttling)
       • queueMicrotask
       • Promise

2. Micro tasks execution vs tasks execution
   According to the processing model algorithm, the micro-tasks execution algorithm is fast and efficient. All it does is to execute all the micro-tasks once the stack is empty (no queue management).

conclusion

Javascript is not a language for heavy computations or recursions logic, but if you need to execute recursive execution as fast as you can,
without stack size limitation, using micro-tasks might help you.