Por que a versão iterativa leva mais tempo?

Respostas:

10

Os dois programas não são equivalentes. A versão recursiva está computando

(... ((1 * 2) * 3) * 4 ... * n)

enquanto o iterativo está computando

(... ((n * (n-1)) * (n-2) ... * 1)

portanto, quantidades intermediárias estão crescendo mais rapidamente para a versão iterativa e o cálculo de grande número é mais rápido quando os números envolvidos são pequenos (a Computação 1000! sem grande num não tem sentido e o dialeto cego muda para grande num automaticamente).

AProgrammer
fonte
1

Quando você cria um algoritmo recursivo iterativo, precisa implementar explicitamente a pilha que rastreia os resultados. Esse ato adiciona operações extras para empurrar e estourar a pilha que o algoritmo recursivo obtém de graça (bem, não de graça, mas as operações extras somam mais do que o custo da recursão).

Michael Brown
fonte
1
Você olhou para os programas? O fatorial iterativo não manipula uma pilha.
AProgrammer
-1

Só posso adivinhar, nem tenho certeza se esses benchmarks são do código C ou SBLC. Meu palpite é que o culpado está mudando a variável. 1000! é um número bastante grande, talvez seja mais rápido preencher a pilha com intermediários e limpar do que criar uma cópia e substituir.

Gabriel Ščerbák
fonte
Aqueles eram do código SBCL, eu acho.
martinjacobd