JavaScript: iteração vs. recursão

Hora da história: recentemente eu tinha um problema pra resolver e queria impressionar fazendo-o da forma mais “elegante” possível. Dito isso, passei algumas boas horas escrevendo um algoritmo recursivo com a menor complexidade possível mas no final enviei um algoritmo iterativo em `O(n²)`. Depois de submeter minha solução, eu fiquei curiosa sobre como JavaScript lidava com recursão vs. iteração e assim surgiu esse post.

Em termos gerais, recursão e iteração fazem as mesmas coisas: resolvem uma tarefa um pedaço por vez. A diferença é que a enquanto a iteração repete uma tarefa até que ela seja completa, a recursão quebra essa tarefa em tarefas menores até que haja uma solução.

Não existe consenso sobre qual método é mais eficiente. Pra ilustrar, veja duas implementações da Sequência de Fibonacci:

A primeira abordagem (recursiva), apesar de mais concisa, tem complexidade `O(2^n)`, enquanto a segunda abordagem (iterativa) tem complexidade `O(n)`. Ou seja, uma é exponencial e a outra linear, com impactos significativemente diferentes em seus tempos de execução.

Nesse momento, você pode estar se perguntando “se a diferença entre uma abordagem e a outra é tão grande, por que a dúvida entre qual escolher?”. O ponto é que existem problemas onde uma abordagem recursiva é mais ideal, por exemplo quando lidamos com ADTs (tipos abstratos de dados), exemplo:

A função acima nos permite facilmente caminhar por todos os nós do DOM (que é um tipo abstrato de dado, talvez eu deva fazer um post sobre data structure em JS? 🤔) e aplicar uma função a cada um deles.

Complexidade e running times de fora, um problema um tanto comum em algoritmos recursivos são as chamadas infinitas, por exemplo uma chamada para um algoritmo fatorial onde `N < 0`. Ou seja, ao trabalhar com abordagens recursivas, deve-se sempre assegurar que um caso base ocorra eventualmente.

Caso haja a possibilidade de que seu algoritmo entre em chamadas infinitas ou até mesmo uma grande quantidade de chamadas, você terá um problema conhecido como Stack Overflow, onde o tamanho da `stack` excede seus próprios limites, causando um crash no seu software.

Uma das maneiras de evitar Stack Overflow em chamadas muito “profundas” é um recurso chamado `tail call optimization` que permite que você faça chamadas em uma função sem crescer o tamanho de sua `stack`, esse recurso foi adotado no EcmaScript 6.

A primeira abordagem, apesar de recursiva, não se adequa ao `tail call optimization` dado que ela retorna o valor de `n` e o resultado da chamada recursiva. Enquanto isso, a segunda abordagem se adequa pois o valor de retorno da função chamada é a única coisa retornada pela função que a chama.

Dadas essas informações, a única conclusão possível é que não há abordagem “bala de prata”, tudo vai depender da implementação e necessidade do seu projeto, afinal performance no front-end é muito mais do que algoritmos e suas complexidades.