Executando verificação de segurança...
Em resposta a O Javascript possui otimização de cauda em funções recursivas?
5
kht

Dúvida: como vc mediu esses tempos? Porque eu testei aqui e não teve essa diferença tão grande. Na verdade os tempos foram bem próximos.

Pergunto porque simplesmente rodar a função uma vez isoladamente (assumindo que esse foi seu teste, mas por favor confirme) raramente é o meio mais confiável, pois tem vários fatores que podem influenciar - por exemplo, a inicialização do runtime, caso use um como o Node.js ou Deno, o próprio console.log (I/O sempre atrapalha essas medições), etc.

Enfim, o ideal é usar alguma ferramenta que elimina ou minimiza esses fatores externos na medição. Eu fiz um teste usando o Benchmark.js, segue o código:

function fatorial(n) {
    if (n == 1 || n == 0) return 1;
    return n * fatorial(n - 1);
}
// mudei o nome, para poder usar ambas no mesmo teste
function fatorial_acc(n, acc = 1) {
    if (n == 1 || n == 0) return acc;
    return fatorial_acc(n - 1, n * acc);
}
const n = 100;

var Benchmark = require('benchmark');
var suite = new Benchmark.Suite;
suite
.add('fatorial', function () { fatorial(n); })
.add('fatorial_acc', function () { fatorial_acc(n); })
.on('complete', function () { console.log('Fastest is ' + this.filter('fastest').map('name')); })
.on('cycle', function (event) { console.log(String(event.target)); })
.run({ 'async': true });

Lembrando que os números exatos podem variar de acordo com o hardware, mas enfim, na minha máquina o resultado foi:

fatorial x 1,009,360 ops/sec ±3.16% (81 runs sampled)
fatorial_acc x 1,023,571 ops/sec ±1.30% (88 runs sampled)
Fastest is fatorial_acc,fatorial

Os números (1,009,360 e 1,023,571) estão em notação americana (a vírgula separa os milhares) e representam a quantidade de operações por segundo (ou seja, quanto maior, melhor). E na prática, houve empate técnico, tanto que ele mostra ambas como a "mais rápida".

Rodando o mesmo teste várias vezes, às vezes a primeira é ligeiramente mais rápida, e às vezes é a segunda. Mas a diferença continua tão pequena que na prática ainda é um empate técnico. Nada chega perto da diferença que vc chegou, por isso pergunto novamente como foi feita a sua medição.

Testando online no jsbench.me, os resultados foram similares (empate técnico, embora curiosamente o primeiro tenha sido um pouco mais rápido na maioria das vezes).

Enfim, respondendo à pergunta, atualmente a maioria das engines não otimizam a recursão em cauda, então não deveria ter tanta diferença assim.

Aliás, uma das respostas disse que o segundo caso não empilha as chamadas, mas não é verdade. Vejamos novamente a função:

function fatorial_acc(n, acc = 1) {
    if (n == 1 || n == 0) return acc;
    return fatorial_acc(n - 1, n * acc);
}

Suponha que eu chame fatorial_acc(3). Então temos:

  • (em fatorial_acc(3)): n é 3 e acc é 1
  • (em fatorial_acc(3)): não entra no if, então retorna fatorial_acc(n - 1, n * acc), ou seja, fatorial_acc(3 - 1, 3 * 1) -> fatorial_acc(2, 3) (é uma chamada recursiva, que é empilhada sim, já que não há otimização em cauda)
    • (em fatorial_acc(2, 3)): agora n é 2 e acc é 3
    • (em fatorial_acc(2, 3)): não entra no if, então retorna fatorial_acc(n - 1, n * acc), ou seja, fatorial_acc(2 - 1, 3 * 2) -> fatorial_acc(1, 6) (é outra chamada recursiva, que é empilhada sim, já que não há otimização em cauda)
      • (em fatorial_acc(1, 6)): agora n é 1 e acc é 6
      • (em fatorial_acc(1, 6)): entra no if, então retorna acc, que no caso é 6
    • (dentro de fatorial_acc(2, 3)): fatorial_acc(1, 6) retornou 6, então o return retorna 6
  • (em fatorial_acc(3)): fatorial_acc(2, 3) retornou 6, então o return retorna 6
  • o resultado é 6

Ou seja, há empilhamento das chamadas recursivas (só não haveria empilhamento se tivesse otimização em cauda).

Só pra completar, segue o empilhamento da primeira:

function fatorial(n) {
    if (n == 1 || n == 0) return 1;
    return n * fatorial(n - 1);
}

Se chamarmos fatorial(3):

  • (em fatorial(3)): n é 3
  • (em fatorial(3)): não entra no if, então retorna n * fatorial(n - 1), ou seja, 3 * fatorial(3 - 1) -> 3 * fatorial(2, 3) (chamada recursiva)
    • (em fatorial(2)): agora n é 2
    • (em fatorial(2)): não entra no if, então retorna n * fatorial(n - 1), ou seja, 2 * fatorial(2 - 1) -> 2 * fatorial(1) (chamada recursiva)
      • (em fatorial(1)): agora n é 1
      • (em fatorial(1)): entra no if, então retorna 1
    • (dentro de fatorial(2)): fatorial(1) retornou 1, então o return retorna 2 * fatorial(1), ou seja, 2
  • (em fatorial(3)): fatorial(2) retornou 2, então o return retorna 3 * fatorial(2), ou seja, 6
  • o resultado é 6

Em ambas a quantidade de empilhamentos é a mesma, já que a quantidade de chamadas recursivas é a mesma. A única diferença é que a versão sem acc precisa multiplicar o resultado da chamada recursiva com n, enquanto a versão com acc já vai passando as multiplicações intermediárias pra frente, então ela só retorna o mesmo valor retornado pela chamada recursiva. Mas a quantidade de chamadas empilhadas é a mesma.

Visualizando a pilha de chamadas

Modifiquei a função para usar console.trace(), que mostra que as chamadas são de fato empilhadas:

function fatorial_acc(n, acc = 1) {
    console.trace('antes if', n, acc);
    if (n == 1 || n == 0) return acc;
    console.trace('antes return', n, acc);
    return fatorial_acc(n - 1, n * acc);
}
const n = 3;

fatorial_acc(n);

A saída foi (eliminei as linhas do próprio Node, deixando apenas as do meu arquivo de testes, para ficar mais fácil visualizar):

Trace: antes if 3 1
    at fatorial_acc (/home/hkotsubo/teste.js:10:13)
    at Object.<anonymous> (/home/hkotsubo/teste.js:17:13)
Trace: antes return 3 1
    at fatorial_acc (/home/hkotsubo/teste.js:12:13)
    at Object.<anonymous> (/home/hkotsubo/teste.js:17:13)
Trace: antes if 2 3
    at fatorial_acc (/home/hkotsubo/teste.js:10:13)
    at fatorial_acc (/home/hkotsubo/teste.js:13:12)
    at Object.<anonymous> (/home/hkotsubo/teste.js:17:13)
Trace: antes return 2 3
    at fatorial_acc (/home/hkotsubo/teste.js:12:13)
    at fatorial_acc (/home/hkotsubo/teste.js:13:12)
    at Object.<anonymous> (/home/hkotsubo/teste.js:17:13)
Trace: antes if 1 6
    at fatorial_acc (/home/hkotsubo/teste.js:10:13)
    at fatorial_acc (/home/hkotsubo/teste.js:13:12)
    at fatorial_acc (/home/hkotsubo/teste.js:13:12)
    at Object.<anonymous> (/home/hkotsubo/teste.js:17:13)

Repare que no final (quando chamamos fatorial_acc(1, 6), que é o caso em que ele entra no if) há 3 chamadas de fatorial_acc empilhadas. O que mostra que de fato não há tail call optmization, e que as chamadas são empilhadas sim.

Mais uma prova de que as chamadas são empilhadas

Alterei o valor de n para 50000:

function fatorial_acc(n, acc = 1) {
    if (n == 1 || n == 0)
        return acc;
    return fatorial_acc(n - 1, n * acc);
}
const n = 50000;
console.log(fatorial_acc(n));

Com isso, ele estoura o limite de chamadas recursivas que o engine suporta, daí o Node.js deu erro, porque a quantidade de chamadas empilhadas estourou o tamanho máximo da pilha:

RangeError: Maximum call stack size exceeded
    at fatorial_acc (/home/hkotsubo/teste.js:11:22)
    at fatorial_acc (/home/hkotsubo/teste.js:11:22)
    at fatorial_acc (/home/hkotsubo/teste.js:11:22)
    ... trocentas linhas iguais

Ou seja, as chamadas são empilhadas sim. No Node.js é possível aumentar o tamanho da pilha através da linha de comando:

node --stack-size=50000 teste.js

Aí ele roda. Como curiosidade, o resultado será Infinity, já que o fatorial de 50000 é um número tão grande que estoura os limites máximos da linguagem.

Por fim, testei no Chrome e Firefox (que atualmente não otimizam), e deu erro também (inclusive, no Firefox a mensagem de erro é "too much recursion").

Carregando publicação patrocinada...
1
LucasMantuan

Muito obrigado pelo tempo gasto nesta explicação. Esclareceu minha dúvida e trouxe muito mais conteúdo... Valeu!

Então, acho quer meu método de medição não foi o mais preciso, utilizei o console.time() e o console.timeEnd().

3
kht
Autor
Autor

Então, testei assim:

function fatorial(n) {
    if (n == 1 || n == 0)
        return 1;
    return n * fatorial(n - 1);
}

function fatorial_acc(n, acc = 1) {
    if (n == 1 || n == 0)
        return acc;
    return fatorial_acc(n - 1, n * acc);
}
const n = 100;

console.time();
fatorial(n);
console.timeEnd();

console.time();
fatorial_acc(n);
console.timeEnd();

Ele diz que fatorial é mais lento. Mas se eu inverter a ordem (chamar fatorial_acc primeiro), ele vai dizer que esse é o mais lento. O primeiro a ser chamado é mais lento, independente da ordem, provavelmente porque no início tem também a inicialização do runtime, warmup do JIT, sabe-se lá mais o que o Node.js deve fazer na carga inicial.

Aliás, se eu fizer algo assim:

for (var i = 0; i < 30; i++) {
    console.time();
    fatorial_acc(n);
    console.timeEnd();
}

Ou seja, chamo a mesma função várias vezes. Mesmo assim, a primeira execução sempre é mais lenta, pelo mesmo motivo. No meu caso, o resultado foi:

default: 0.434ms
default: 0.027ms
default: 0.038ms
... as demais foram abaixo de 0.1ms

E se eu mudar o for acima para chamar somente fatorial, o resultado é o mesmo: a primeira é bem mais lenta.

Por isso é melhor usar ferramentas que desconsideram esses fatores externos (como eu fiz com o Benchmark.js, por exemplo).