Dlaczego wersja iteracyjna trwa dłużej?

Odpowiedzi:

10

Te dwa programy nie są równoważne. Wersja rekurencyjna jest obliczeniowa

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

podczas gdy iteracyjny jest komputer

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

dlatego ilości pośrednie rosną szybciej w wersji iteracyjnej, a obliczanie dużej liczby jest szybsze, gdy zaangażowane liczby są małe (Obliczanie 1000! bez dużej liczby nie ma sensu, a dialp sepu automatycznie przełącza się na dużą liczbę).

AProgrammer
źródło
1

Kiedy tworzysz iteracyjny algorytm rekurencyjny, musisz jawnie zaimplementować stos, który śledzi wyniki. Ten akt dodaje dodatkowe operacje związane z wypychaniem i zrzucaniem stosu, który algorytm rekurencyjny otrzymuje za darmo (no nie całkiem za darmo, ale dodatkowe operacje sumują się więcej niż koszt rekurencji).

Michael Brown
źródło
1
Czy oglądałeś programy? Czynnik iteracyjny wcale nie manipuluje stosem.
AProgrammer
-1

Mogę tylko zgadywać, nie jestem nawet pewien, czy te testy porównawcze pochodzą z kodu C czy z kodu SBLC. Domyślam się, że sprawca mutuje zmienną. 1000! jest dość dużą liczbą, być może szybsze jest zapełnienie stosu pośredniczącymi i wyczyszczenie niż utworzenie kopii i zastąpienie.

Gabriel Ščerbák
źródło
Sądzę, że pochodzą z kodu SBCL.
martinjacobd