Patrzyłem na http://programming.lispdream.com/blog/2011/06/recursion-vs-iteration/ i zobaczyłem, że po jego implementacji rekurencyjnych i iteracyjnych implementacji funkcji silniowej iteracja faktycznie trwa dłużej podane n = 1000. Nie mogę zrozumieć, dlaczego (nie wyjaśnia, ale mówi, że jest to ćwiczenie dla czytelnika). Przepraszam za moją nowość w tym wszystkim.
Odpowiedzi:
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ę).
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).
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.