Bem, pelo que eu li, não. Mas porque as funções abaixo executam em um tempo tão diferente (estou utilizando o Node 19.7)?
Esta função executa em: 6.311ms
function fatorial(n) {
if (n == 1 || n == 0) return 1;
return n * fatorial(n - 1);
}
console.log(fatorial(100));
E esta em 0.09ms:
function fatorial(n, acc = 1) {
if (n == 1 || n == 0) return acc;
return fatorial(n - 1, n * acc);
}
console.log(fatorial(100));
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:
fatorial_acc(3)): n é 3 e acc é 1fatorial_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)
fatorial_acc(2, 3)): agora n é 2 e acc é 3fatorial_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)
fatorial_acc(1, 6)): agora n é 1 e acc é 6fatorial_acc(1, 6)): entra no if, então retorna acc, que no caso é 6fatorial_acc(2, 3)): fatorial_acc(1, 6) retornou 6, então o return retorna 6fatorial_acc(3)): fatorial_acc(2, 3) retornou 6, então o return retorna 66Ou 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):
fatorial(3)): n é 3fatorial(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)
fatorial(2)): agora n é 2fatorial(2)): não entra no if, então retorna n * fatorial(n - 1), ou seja, 2 * fatorial(2 - 1) -> 2 * fatorial(1) (chamada recursiva)
fatorial(1)): agora n é 1fatorial(1)): entra no if, então retorna 1fatorial(2)): fatorial(1) retornou 1, então o return retorna 2 * fatorial(1), ou seja, 2fatorial(3)): fatorial(2) retornou 2, então o return retorna 3 * fatorial(2), ou seja, 66Em 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.
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.
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").
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().
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).
A linguagem não tem. Em especificação do EcmaScript (o nome real da linguagem) não exige isto, portanto depende da implementação, tem que ver se o engine que está usando está faz ou não.
O nome JavaScript originalmente foi criado pela Netscape, depois herdado pela Mozilla, ainda que todos usam o nome dele como se fosse o oficial da linguagem.
A otimização chamada Tail Call Elimination deve estar presente em algum engine mais padrão (o que achei depois foi o Safari, nenhum outro, mas pode existir).
De qualquer forma essa otimização não existe para fazer o código ficar mais rápido, ela apenas impede que seja criada uma pilha enorme sendo que em cada chamada tem que reservar espaço para a variável, o que em alguns casos vai estourar o limite da pilha (o tal do stack overflow). Fazendo isso, colateralmente, a performance ficará melhor.
Se um executou muito rápido e o outro não, significa que deve ter alguma otimização, mas não em todas as situações. Eu nem garanto que essa seja a causa, pode ser até outra otimização.
O JITter poderia ter achado um meio de otimizar em um e não no outro, eu diria que é o mais provável. A resposta do kht dá detalhes que podem indicar isso. Ele fala em medir o tempo de carga de um e não do outro. Eu vou mais além, pode ter ocorrido até mesmo o tempo de warm-up do JITter. E é provável que as bibliotecas que ele usou sabe como lidar com isso e só medir o que importa, descartando esse tempo, e principalmente já descartar o tempo de carga do runtime e compilação. Portanto pode ter ocorrido umamedida errada.
Poderia ser que só faça a otimização quando faz a chamada simples da mesma função (segundo caso), mas quando a chamada está contida dentro de uma expressão (primeiro caso) não faça. No fim, vemos lá na resposta do kht que as chamas não são otimizadas nos dois casos.
No geral, se tiver uma otimização, ótimo, se não tiver, é ok. Só entenda que não pode contar com ela, ninguém é obrigado a garantir isso, e se não tiver e seu código estourar a pilha é problema seu, não é questão de performance, que pode ser um problema extra.
Ainda considerando que poderia ter ocorrido otimização, você experimentou com o V8 (pelo menos o usado nessa versão do Node) e viu esse resultado, mas pode mudar, otimização não é algo que deve se valer, a não ser que esteja em especificação e todos os engines que você usa estejam comprometidos a se conformar. Novamente, não foi o TCE que aconteceu.
De fato, até onde pesquisei, o V8 não faz essa eliminação, mas pode ter mudado recentemente para casos triviais.
Nada indica que uma empilha e a outra não, pelo menos de forma natural. E de fato na última edição do kht fica claro que ambas chamam igual.
É possível garantir a eliminação com uma técnica de trampolim, mas pra quê?
O melhor a fazer é usar um loop, ele é rápido e mais garantido. Só use recursão quando ela for primordial. Inclusive o loop também costuma ser melhor que fazer um mapeamento, mesmo que a moda seja usar o jeito "mais bonitinho".
Faz sentido para você?
Espero ter ajudado.
Farei algo que muitos pedem para aprender a programar corretamente, gratuitamente. Para saber quando, me segue nas suas plataformas preferidas. Quase não as uso, não terá infindas notificações (links aqui).
Resposta simples os motores JS existentes e mais conhecidos não tem otimizações para funções recursivas!
Então é melhor não usar!
O JS(especificação EcmaScript) em si não diz nada sobre nenhum tipo de otimização!
Tudo depende dos motores!