Otimização da recursão da cauda do JavaScript

Olá leitor.

Às vezes, para resolver o problema, é necessário usar a recursão , que tem seus prós e contras. Corri para o problema de estouro de pilha.

A profundidade máxima da recursão é limitada pelo mecanismo JavaScript. Você pode contar com precisão com 10.000 chamadas aninhadas, alguns intérpretes permitem mais, mas para a maioria delas, 100.000 chamadas estão além do escopo dos recursos. Existem otimizações automáticas que ajudam a evitar o transbordamento da pilha de chamadas ("otimização da recursão de cauda"), mas elas ainda não são suportadas em todos os lugares e funcionam apenas em casos simples.

Um exemplo de uma função recursiva:

function sum(n) { return n === 0 ? 0 : n + sum(n - 1) } sum(5) // 1 + 2 + 3 + 4 + 5 = 15 sum(100000) // Error: Maximum call stack size exceeded. 

A recursão da cauda permite otimizar as chamadas do compilador e já está no padrão ES6 , mas o suporte ao navegador deixa muito a desejar .

Um exemplo de uma função recursiva da cauda:

 function sum(number, s = 0){ return number === 0 ? s : sum(number - 1, s + number) } 

Mas, sem o suporte do navegador, enfrentaremos o mesmo problema - estouro de pilha. Podemos tentar usar junto com o trampolim .

Escreveremos um decorador que aceitará a função recursiva modificada (próxima etapa) e a executaremos em um loop, sem aumentar a profundidade da chamada.

 function trampoline(fn) { return function(...args) { let result = fn.apply(fn.context, args) while (typeof result === 'function') { result = result() } return result } } 

Agora nossa função recursiva deve retornar uma função que será imediatamente executada pelo decorador. Dessa maneira, criaremos condicionalmente uma matriz de funções e as executaremos sucessivamente. Mas como retornamos uma nova função anônima a cada vez, esse código funcionará um pouco mais devagar.

 function sum(number, s = 0) { return number === 0 ? s : () => sum(number - 1, s + number) } 

Nós usamos:

 const trampolineSum = trampoline(sum) trampolineSum(100000) // 5000050000 

Este é o meu primeiro artigo. Tentei não recontar os conceitos e forneci um link para as fontes. O tópico não é exclusivo e existe há muito tempo em sites em inglês, infelizmente não o encontrei em russo.

Obrigado pela atenção. Tenha um bom dia :)

Update
Desempenho:

# 1 Recursão




Iteração nº 2




# 3 Recursão da cauda e trampolim




# 4 Recursão da cauda e trampolim (um grande número)




De acordo com os resultados, vemos que o nosso decorador, embora nos permita evitar o erro de estouro de pilha, mas funciona mais lentamente que a versão recursiva e iterativa. Portanto, esse método deve ser usado apenas se você não puder substituir a recursão pela iteração ou tiver medo de estouros de pilha ao executar sua função recursiva.