JavaScript é uma linguagem multiparadigma suportando os paradigmas da orientação a objetos e o funcional. Não é raro desenvolvedores mais voltados para o paradigma funcional se valerem de recursão para solucionar problemas. Porém, pela ausência de tail call optimization (TCO) nas engines do mercado, longas chamadas recursivas podem estourar a call stack terminando abruptamente o programa. Neste artigo aprenderemos a utilizar recursão sem medo na ausência de TCO através do pattern Trampoline. Primeiro, veremos um pouco sobre recursão e os problemas que podem acontecer. Depois, uma breve introdução a TCO para no final implementarmos o pattern Trampoline.

O problema

Vamos começar com um problema simples. Temos a função showCountDown que exibe regressivamente todos os números a partir do número fornecido:

const showCountDown = counter => {
  while(counter >= 0) {
    console.log(counter--);
  }
};
showCountDown(3);
/* exibe
3
2
1
*/

Podemos resolver o mesmo problema através de recursão.

Um pouco sobre recursão

É possível refatorar a função showCountDown para uma versão recursiva. Vejamos:

const showCountDown = counter => {
  if (counter < 0) return;
  console.log(counter);
  showCountDown(--counter);
};
showCountDown(3); // mesmo comportamento

Uma função recursiva nada mais é do que uma função que chama a si mesma. Todavia, é preciso haver um leave event para indicar o fim da recursão retornando um valor ou não. Em nosso caso, a instrução if (counter < 0) return; realiza esse papel.

Que tal um exemplo de uma chamada recursiva que no fim retorne um valor? É o que veremos a seguir.

Chamada recursiva com retorno

Um exemplo clássico de chamada recursiva com retorno é o batido, mas nem por isso menos importante, cálculo fatorial. Vejamos um exemplo:

const factorial = n => {
    // fatorial de 0 é 1!
    if(n <= 1) return 1
    // return aqui!
    return n * factorial(--n);
};
console.log(factorial(3)) // 6;

É importante que o leitor resolva mentalmente a chamada recursiva anterior. O entendimento adquirido será a chave para compreender a TCO e o pattern Trampoline.

No código anterior, uma chamada à factorial(3) realizará mais duas chamadas à função factorial. Mas como isso aparece na call stack? Aliás, o que seria essa call stack?

A call stack (pilha de chamadas) é composta de uma ou mais stack frames. Cada stack frame corresponde a uma chamada para uma função que ainda não terminou, isto é, que ainda não retornou.

Cada chamada recursiva adiciona uma stack frame à call stack até chegar ao leave event. A partir daí, começam a ser removidas à media que retornam seus resultados. Visualmente temos algo assim:

factorial(1) // 3 chamada
factorial(2) // 2 chamada
factorial(3) // 1 chamada

Quando factorial(1) for chamado, o leave event retornará 1 terminando a chamada recursiva. Isso fará com que cada stack frame seja removida da pilha:

factorial(1) // 3 chamada / primeira a ser removida
factorial(2) // 2 chamada / segunda a ser removida
factorial(3) // 1 chamada / terceira a ser removida, retornando o fatorial

Graficamente temos:

       ---|---
   ---|       |--- 
---               ---

Porém, há um limite máximo de stack frames na call stack que ao ser excedido fará o programa terminar abruptamente. Que tal irmos além da capacidade da call stack para vermos o que acontece?

Ultrapassando o tamanho máximo da call stack

Vamos voltar ao exemplo do cálculo fatorial, mas desta vez utilizaremos 20000 como argumento da função:

// código anterior omitido
console.log(factorial(20000)); 
// Uncaught RangeError: Maximum call stack size exceeded

Passamos do limite suportado pela call stack, isto é, estouramos a pilha de execução do nosso programa! Podemos fazer o mesmo com a função showCountDown:

// código anterior omitido
showCountDown(20000);
// Uncaught RangeError: Maximum call stack size exceeded

E agora? Uma solução é adequarmos nossa chamada recursiva para que se benficie da tail call optimization (TCO).

Alguns autores chamam de tail call elimination (TCE).

Mas o que seria essa tal TCO e como ela pode nos ajudar?

Tail Call Optimization

A tail call optimization (TCO) ocorre quando o interpretador vê que a chamada de função recorrente é a última coisa na função a ser executada e não há nenhuma outra operação que precisa ser aplicada ao resultado retornado da função.  A chamada para a função corrente é feita via “jump” e não por meio de uma chamada de “subrotina”. Em outras palavras, o interpretador otimiza a recursão eliminando a última chamada de função da call stack.

O exemplo abaixo, que estouraria a call stack em uma engine JavasScript sem TCO rodará indefinidamente sem provocar o estouro por uma engine com suporte a TCO:

const fn = () => fn();
fn();
// -> Engine COM TCO: loop infinito
// -> Engine SEM TCO: Uncaught RangeError: Maximum call stack size exceeded

E nossa função factorial? Ela não se coaduna com a exigência da TCO, pois seu retorno é n * factorial(--n); e não a chamada de uma função apenas.

A função factorial, adequada à TCO fica assim:

// acc é o acumulador do resultado
const factorial = (acc, n) => {
    if(n <= 1) return acc;
    // agora retorna a chamada da função
    return factorial(acc * n, --n);
};
console.log(factorial(1, 3)) // 6;

Tudo muito bonito, só não é perfeito porque as engines JavaScript não suportam TCO! Como assim?

Sem suporte a TCO nas engines JavaScript

A implementação da TCO faz parte do ES2015 (E6), porém os browsers vendors a deixaram de lado por questões de segurança que só apareceram durante a sua implementação. Você pode saber mais sobre este episódio no podcast “Evolução e Especificação do JavaScript Moderno”, realizado por hipsters.tech.

A boa notícia é que mesmo sem as engines JavaScript suportarem TCO, podemos evitar o estouro da call stack por meio de recursão através do pattern Trampoline.

Trampoline pattern

O pattern Trampoline (trampolim, em português) é um loop que invoca funções que envolvem outras funções.

Uma função que envolve outra função é chamada de thunk.

A função trampoline é implementada através de uma função que recebe outra função como argumento:

// função que recebe outra como argumento
const trampoline = fn => {
/* implementação do trampoline */
};

A função trampoline chamará repetidamente a função fn recebida como parâmetro até que o retorno da função não seja um thunk:

const trampoline = fn => {
  // faça enquanto for uma função
  while (typeof fn === 'function') {
      // chama a função repetidas vezes
      fn = fn();
  }
  // só retornada quando fn não for uma função!
  return fn;
};

Durante as chamadas sucessivas da função original, se algum valor que não for uma função for retornado, o trampoline parará imediatamente sua execução retornando o resultado da última chamada da função fn recebida como parâmetro.

Implementar a função trampoline não é suficiente. A função factorial que adequamos à TCO precisa retornar uma função (thunk) que ao ser invocada executará a operação recursiva:

const factorial = (acc, num) => {
  if(num <= 1) return acc;
  // retorna uma função que ao ser chamada retorna 
  // a chamada de factorial
  return () => factorial(acc * num, --num);
}

Por fim, um teste que antes estourava a call stack:

// infity, sem estourar a pilha
console.log(trampoline(factorial(1, 20000)));

O ato de converter uma função para suportar trampoline é chamado de trampolining

A função trampoline existe apenas para controlar a execução de forma iterativa garantindo que haja apenas um stack frame em qualquer momento. Todavia, o código não executa tão rápido quanto sua versão recursiva, além de precisarmos ajustar a função para fazer uso do trampoline.

Vejamos a função showCountDown modificada para ser utilizada por trampoline:

const showCountDown = counter => {
  if (counter < 0) return;
  console.log(counter);
  // antes era "return showCountDown(--counter)",
  // agora retorna uma função
  return () => showCountDown(--counter);
};
// exibe o contador sem estourar a pilha
trampoline(showCountDown(20000));

Conclusão

Por mais que a TCO tenha sido proposta no ES2015 (ES6) sua implementação ainda não chegou nas engines dos navegadores do mercado por ter criado brechas de seguança, inclusive na plataforma Node.js. Porém, sua ausência pode ser contornada através do pattern Trampoline que exige uma ligeira modificação no código original. Todavia, o uso do pattern não é tão performático quanto o suporte nativo à TCO.

E você? Já passou pelos problemas aqui descritos? Implementou ou utilizou alguma biblioteca para aplicar o pattern Trampoline? Deixe sua opinião.