Recursão e pilha de chamadas em JavaScript

A recursão é um conceito fundamental em JavaScript que permite que funções chamem a si mesmas. Esse método é essencial para resolver problemas que podem ser divididos em tarefas mais simples e repetitivas. Este artigo oferece uma visão abrangente da recursão, explorando o contexto de execução, a pilha de chamadas e suas aplicações na travessia de estruturas recursivas.

O que é recursão?

Na programação, recursão é um método em que uma função chama a si mesma uma ou mais vezes até que uma condição especificada seja atendida; nesse ponto, o restante de cada repetição é processado. Toda função recursiva é composta por exatamente duas partes:

1. Caso base: a condição em que a função para de chamar a si mesma e retorna um valor diretamente. Sem um caso base, a função chamaria a si mesma indefinidamente.
2. Caso recursivo: quando o caso base não é atendido, a função chama a si mesma novamente com um argumento menor ou mais simples, que a aproxima do caso base.

A regra mais importante da recursão: toda chamada recursiva deve avançar em direção ao caso base. Se isso não acontecer, ocorre uma recursão infinita e o programa falha com um estouro de pilha (stack overflow).

Aqui está o menor exemplo útil possível — somar os números de 1 a n:

Para calcular sumTo(5), a função precisa de sumTo(4), que precisa de sumTo(3), e assim por diante até sumTo(1), que retorna 1 diretamente. A cadeia então se desfaz: cada chamada soma o próprio número e devolve o resultado a quem a chamou.

A mesma lógica sempre pode ser escrita com um loop. Compare a versão recursiva acima com esta versão iterativa:

Ambas produzem o mesmo resultado. A versão recursiva é mais curta e se aproxima mais da definição matemática; a versão iterativa usa uma única chamada de função e uma quantidade fixa de memória. Comparamos as duas com mais detalhes em Recursão vs iteração mais adiante.

Contexto de execução e a pilha de chamadas

Quando uma função é executada em JavaScript, o motor cria um contexto de execução (às vezes chamado de quadro de pilha, ou stack frame): um registro interno que guarda as variáveis locais da chamada, seus parâmetros e a linha exata em que a execução se encontra.

A pilha de chamadas (call stack) é uma pilha desses quadros. Ela funciona no modelo "o último a entrar é o primeiro a sair":

• Quando uma função é chamada, seu quadro é empilhado (push) no topo da pilha.
• Quando uma função retorna, seu quadro é desempilhado (pop), e o controle volta ao quadro logo abaixo — exatamente do ponto em que ele havia parado.

Na recursão, cada chamada à função empilha um quadro totalmente novo, com sua própria cópia dos parâmetros. Assim, sumTo(3) produz três quadros empilhados antes que qualquer um deles retorne:

sumTo(1)   ← top of stack, returns 1 first
sumTo(2)
sumTo(3)   ← bottom, the original call, returns last

Quando sumTo(1) atinge o caso base e retorna, seu quadro é desempilhado, sumTo(2) retoma a execução e retorna, e depois sumTo(3). É por isso que a profundidade da recursão determina diretamente quanta memória a pilha de chamadas utiliza: n chamadas recursivas significam n quadros ativos ao mesmo tempo.

Exemplo: sonhos aninhados

Imagine um cenário em que um personagem de uma história adormece e sonha que é outra pessoa, que por sua vez adormece para sonhar com outro personagem, e assim por diante. Cada nível de sonho representa uma chamada recursiva, e acordar de cada nível de sonho representa desempilhar um contexto de execução da pilha de chamadas.

Na função dream(level) acima, o caso base e o caso recursivo estão claramente definidos:

• Caso base: ocorre quando level === 0. É a condição que impede a recursão de continuar indefinidamente. Nesse caso, quando level chega a 0, a função imprime "Wake up!" e deixa de fazer novas chamadas recursivas.
• Caso recursivo: é definido quando level > 0. Nessa situação, a função imprime o level atual e depois chama a si mesma novamente com level - 1, reduzindo o level em uma unidade a cada chamada. Isso continua até que a condição do caso base seja atendida.

Essas duas partes trabalham juntas para garantir que a função seja executada corretamente e termine em algum momento.

Travessias recursivas

A travessia recursiva é uma técnica frequentemente usada com estruturas que contêm vários níveis de objetos aninhados, como árvores ou diretórios. Esse método é ideal para realizar operações como busca ou para construir uma estrutura visual a partir de componentes aninhados.

Exemplo: travessia de um sistema de arquivos

Veja como você poderia usar recursão para percorrer um sistema de arquivos, listando todos os arquivos de cada diretório:

Na função listFiles(directory), a recursão consiste em percorrer a estrutura de diretórios:

• Caso base: curiosamente, a condição de parada dessa função não é declarada explicitamente como um caso base tradicional (como uma instrução if que encerra a recursão). Em vez disso, ela deixa de recorrer naturalmente ao encontrar um diretório sem outros subdiretórios (ou seja, quando directory.directories é um array vazio). Isso acontece porque o método forEach em um array vazio não resulta em nenhuma nova chamada recursiva.
• Caso recursivo: o caso recursivo é invocado explicitamente com directory.directories.forEach(listFiles);. Isso ocorre quando um diretório contém um ou mais subdiretórios, e listFiles é chamada recursivamente para cada subdiretório. Cada chamada recursiva processa os arquivos e diretórios dentro daquele subdiretório, aprofundando-se na estrutura até que não haja mais subdiretórios (caso base implícito).

Essa função demonstra de forma eficaz como a recursão pode navegar por estruturas aninhadas complexas, chamando a si mesma para tratar tarefas semelhantes em cada nível de aninhamento.

Estruturas recursivas

Estruturas recursivas são estruturas autorreferentes, em que cada parte é definida em termos de partes semelhantes. Exemplos comuns incluem organogramas, árvores binárias e muito mais.

Exemplo: organograma

Considere um organograma em que cada gerente pode ter vários subordinados, que por sua vez também podem ser gerentes.

Na função showOrgChart(employee), a recursão é estruturada para exibir um organograma:

• Caso base: assim como no exemplo anterior de listFiles, o caso base não é declarado explicitamente como um ponto de parada condicional na função. Em vez disso, a recursão termina naturalmente quando um funcionário não tem subordinados (employee.subordinates é um array vazio). O método forEach não executa nenhuma iteração quando o array está vazio, portanto nenhuma nova chamada recursiva é feita.
• Caso recursivo: o comportamento recursivo ocorre na linha employee.subordinates.forEach(showOrgChart). Isso significa que, sempre que um funcionário tem um ou mais subordinados, a função é chamada recursivamente para cada um deles. Essa recursão desce pela hierarquia, registrando o nome e o cargo de cada subordinado, até chegar a funcionários sem subordinados (caso base implícito).

Essa função demonstra com clareza como a recursão pode ser usada para percorrer e exibir estruturas hierárquicas, como organogramas, em que cada nível de recursão se aprofunda mais na estrutura.

Recursão vs iteração

Qualquer função recursiva pode ser reescrita como um loop, e qualquer loop pode ser reescrito como recursão. Escolher entre os dois é uma questão de compromisso:

Uma boa regra prática: recorra à recursão quando os próprios dados forem recursivos (árvores, objetos aninhados, o sistema de arquivos) e use um loop quando você apenas repete um passo um número conhecido de vezes. O fatorial abaixo é naturalmente recursivo, mas um loop o resolve igualmente bem — e suporta entradas muito maiores:

Estouro de pilha e limites de profundidade

Como cada chamada recursiva adiciona um quadro à pilha de chamadas, a recursão é limitada pela profundidade que a pilha pode atingir. Todo motor JavaScript tem um tamanho máximo de pilha (o número exato varia conforme o motor e a plataforma — geralmente de alguns milhares a dezenas de milhares de quadros). Se esse limite for excedido, o programa lança o erro:

RangeError: Maximum call stack size exceeded

As duas causas mais comuns são um caso base ausente ou inalcançável (recursão infinita) e uma recursão legitimamente profunda sobre um conjunto de dados muito grande. Este exemplo omite deliberadamente um caso base funcional para que a pilha se encha:

Para evitar estouros de pilha:

• Sempre inclua um caso base que a recursão tenha garantia de alcançar.
• Para problemas muito profundos ou sem limite definido, converta a recursão em um loop, que não tem esse limite de profundidade.
• Para estruturas de dados que podem ter profundidade arbitrária, considere uma pilha explícita (um array no qual você usa push/pop) em vez da pilha de chamadas.

Quando usar recursão

A recursão é particularmente útil quando você consegue dividir uma tarefa em subtarefas menores e semelhantes à tarefa original. Ela é poderosa para:

• Ordenar dados (como no merge sort ou no quicksort)
• Percorrer árvores, grafos e iteráveis aninhados
• Manipular dados estruturados complexos, como JSON ou o DOM

No entanto, é fundamental garantir que cada chamada recursiva avance em direção ao caso base, para evitar recursão infinita e possíveis erros de estouro de pilha.

Tópicos relacionados

• Funções JavaScript — como as funções são declaradas e chamadas.
• Function Expressions — funções armazenadas em variáveis, que as funções recursivas costumam usar.
• Iteráveis — a travessia recursiva combina naturalmente com dados iteráveis.
• Loops em JavaScript — a alternativa iterativa à recursão.

Conclusão

Entender a recursão e a pilha de chamadas em JavaScript aumenta sua capacidade de resolver problemas complexos de forma eficiente e eficaz. Com a prática, a recursão pode se tornar uma ferramenta valiosa no seu arsenal de programação, permitindo que você escreva um código mais limpo e eficiente. Seja percorrendo estruturas de dados ou implementando algoritmos complexos, dominar a recursão certamente elevará suas habilidades de programação.

Prática