Lógica de tail call optimization (TCO) sem TCO
Como todos nós sabemos, existe pouca adoção de tail call optimization (TCO) dentro das JavaScript engines atualmente no mercado. Mas como poderíamos então implementar uma lógica (que inicialmente usa recursão) sem estourar a callstack do navegador? Até onde eu sei, existem duas maneiras de fazer isso. Com uma técnica chamada trampoline (não explicarei nesse post) Com generator functions (foco desse post) Vou apenas elencar um exemplo de implementação e futuramente (não agora) vou explicar cada detalhe dessa abordagem. A lógica abaixo soma, através de recursão, todos os elementos presentes dentro de um array: function sum(nums) { if (nums.length === 0) { return 0; } return nums[0] + sum(nums.slice(1)); } Esse código acima estoura a pilha de execução a partir de um determinado tamanho de array. Dentro do Node (na versão v23.6.0), que usa V8 como engine e presente aqui em meu sistema operacional, esse estouro de pilha de execução aconteceu a partir de 15226 elementos. Com function generators e sem recursão, separei em duas functions o trabalho necessário para conseguir executar essa lógica, podendo o array até ter mais elementos: function makeGenerator() { "use strict"; return function* (nums) { let acc = 0; for (let item of nums) { yield; acc += item; } return acc; } } function pickGeneratorReturn(gen) { let obj; do { obj = gen.next(); } while(!obj.done); return obj.value; } Agora experimente executar a soma anterior, mas talvez com... digamos... 100000 elementos
Como todos nós sabemos, existe pouca adoção de tail call optimization (TCO) dentro das JavaScript engines atualmente no mercado.
Mas como poderíamos então implementar uma lógica (que inicialmente usa recursão) sem estourar a callstack do navegador?
Até onde eu sei, existem duas maneiras de fazer isso.
- Com uma técnica chamada trampoline (não explicarei nesse post)
- Com generator functions (foco desse post)
Vou apenas elencar um exemplo de implementação e futuramente (não agora) vou explicar cada detalhe dessa abordagem.
A lógica abaixo soma, através de recursão, todos os elementos presentes dentro de um array:
function sum(nums) {
if (nums.length === 0) {
return 0;
}
return nums[0] + sum(nums.slice(1));
}
Esse código acima estoura a pilha de execução a partir de um determinado tamanho de array.
Dentro do Node (na versão v23.6.0), que usa V8 como engine e presente aqui em meu sistema operacional, esse estouro de pilha de execução aconteceu a partir de 15226 elementos.
Com function generators e sem recursão, separei em duas functions o trabalho necessário para conseguir executar essa lógica, podendo o array até ter mais elementos:
function makeGenerator() {
"use strict";
return function* (nums) {
let acc = 0;
for (let item of nums) {
yield;
acc += item;
}
return acc;
}
}
function pickGeneratorReturn(gen) {
let obj;
do {
obj = gen.next();
} while(!obj.done);
return obj.value;
}
Agora experimente executar a soma anterior, mas talvez com... digamos... 100000 elementos
