JS - Microtask Recursion Trick
Published: 2020-10-04 16:06:03



>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](https://developer.mozilla.org/en-US/docs/Web/JavaScript/EventLoop)

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](https://jsfiddle.net/fyL6u8ws/)*

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:

```javascript
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.

```javascript
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](https://jsfiddle.net/46r1tfyv/)
			- [setInterval](https://jsfiddle.net/qLzyxo3e/)
		- Micro task examples (no throttling)
			- [queueMicrotask](https://jsfiddle.net/tja5fcs0/)  
			- [Promise](https://jsfiddle.net/csny2e0j/)

2.  *Micro tasks execution vs tasks execution*
According to the [processing model algorithm](https://html.spec.whatwg.org/multipage/webappapis.html#event-loop-processing-model), [the micro-tasks execution](https://html.spec.whatwg.org/multipage/webappapis.html#perform-a-microtask-checkpoint) 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.