Te inne odpowiedzi są nieco mylące. Zgadzam się, że podają szczegółowe informacje na temat implementacji, które mogą wyjaśnić tę rozbieżność, ale przeceniają sprawę. Jak poprawnie zasugerował jmite, są one zorientowane na implementację w kierunku zepsutych implementacji wywołań / rekurencji funkcji. Wiele języków implementuje pętle za pomocą rekurencji, więc ewidentnie pętle nie będą szybsze w tych językach. Rekurencja nie jest w żaden sposób mniej wydajna niż zapętlenie (gdy oba mają zastosowanie) w teorii. Pozwólcie mi zacytować streszczenie artykułu Guya Steele'a z 1977 r. Obalenie mitu „Drogiego wezwania do postępowania” lub implementacji procedur uważanych za szkodliwe lub Lambda: ostateczne GOTO
Folklor stwierdza, że oświadczenia GOTO są „tanie”, podczas gdy wywołania procedur są „drogie”. Ten mit jest w dużej mierze wynikiem źle zaprojektowanych implementacji językowych. Rozważany jest historyczny rozwój tego mitu. Omawiane są zarówno pomysły teoretyczne, jak i istniejące wdrożenie, które obalają ten mit. Pokazano, że nieograniczone stosowanie wywołań procedur zapewnia dużą swobodę stylistyczną. W szczególności każdy schemat blokowy można zapisać jako program „strukturalny” bez wprowadzania dodatkowych zmiennych. Trudność związana z instrukcją GOTO i wywołaniem procedury charakteryzuje się konfliktem między abstrakcyjnymi koncepcjami programowania a konkretnymi konstrukcjami językowymi.
„Konflikt między abstrakcyjnymi pojęciami programowania a konkretnymi konstrukcjami językowymi” wynika z faktu, że większość modeli teoretycznych, na przykład nietypowego rachunku lambda , nie ma stosu . Oczywiście ten konflikt nie jest konieczny, jak ilustruje powyższy artykuł i co pokazują również języki, które nie mają mechanizmu iteracji innego niż rekurencja, takiego jak Haskell.
fixfix f x = f (fix f) x( λ x . M) N⇝ M.[N/ x][ N/ x]xM.N.⇝
Teraz na przykład. Zdefiniuj factjako
fact = fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1
Oto ocena tego fact 3, gdzie dla zwięzłości użyję gjako synonimu fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)), tj fact = g 1. To nie wpływa na mój argument.
fact 3
~> g 1 3
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 1 3
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 1 3
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 1 3
~> (λn.if n == 0 then 1 else g (1*n) (n-1)) 3
~> if 3 == 0 then 1 else g (1*3) (3-1)
~> g (1*3) (3-1)
~> g 3 2
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 3 2
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 3 2
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 3 2
~> (λn.if n == 0 then 3 else g (3*n) (n-1)) 2
~> if 2 == 0 then 3 else g (3*2) (2-1)
~> g (3*2) (2-1)
~> g 6 1
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 1
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 1
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 1
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 1
~> if 1 == 0 then 6 else g (6*1) (1-1)
~> g (6*1) (1-1)
~> g 6 0
~> fix (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) 6 0
~> (λf.λa.λn.if n == 0 then a else f (a*n) (n-1)) g 6 0
~> (λa.λn.if n == 0 then a else g (a*n) (n-1)) 6 0
~> (λn.if n == 0 then 6 else g (6*n) (n-1)) 0
~> if 0 == 0 then 6 else g (6*0) (0-1)
~> 6
Z kształtu widać, nawet nie patrząc na szczegóły, że nie ma wzrostu i każda iteracja potrzebuje takiej samej ilości miejsca. (Technicznie, wynik liczbowy rośnie, co jest nieuniknione i tak samo prawdziwe dla whilepętli.) Przeciwstawiam się, aby wskazać tutaj na nieograniczająco rosnący „stos”.
Wydaje się, że archetypiczna semantyka rachunku lambda już robi to, co jest powszechnie nazywane „optymalizacją wywołania ogona”. Oczywiście nie ma tu miejsca „optymalizacja”. Nie ma tutaj specjalnych zasad dla połączeń „ogonowych” w przeciwieństwie do „normalnych” połączeń. Z tego powodu trudno jest podać „abstrakcyjną” charakterystykę tego, co robi „optymalizacja” wywołania ogona, ponieważ w wielu abstrakcyjnych charakterystykach semantyki wywołania funkcji nie ma nic do zrobienia w „optymalizacji” wywołania ogona!
To, że analogiczna definicja fact„przepełnienia stosu” w wielu językach jest brakiem prawidłowego wdrożenia semantyki wywołań funkcji przez te języki. (Niektóre języki mają wymówkę). Sytuacja jest w przybliżeniu analogiczna do implementacji języka, która implementowała tablice z listami połączonymi. Indeksowanie do takich „tablic” byłoby wówczas operacją O (n), która nie spełnia oczekiwań tablic. Gdybym wykonał osobną implementację języka, który używał prawdziwych tablic zamiast połączonych list, nie powiedziałbym, że zaimplementowałem „optymalizację dostępu do tablicy”, powiedziałbym, że naprawiłem zepsutą implementację tablic.
Odpowiadając na odpowiedź Veedrac. Stosy nie są „fundamentalne” dla rekurencji . W zakresie, w jakim zachowanie „przypominające stos” występuje podczas oceny, może się to zdarzyć tylko w przypadkach, w których pętle (bez struktury danych pomocniczych) nie miałyby zastosowania w pierwszej kolejności! Innymi słowy, mogę zaimplementować pętle z rekurencją o dokładnie takiej samej charakterystyce wydajności. Rzeczywiście, Scheme i SML zawierają konstrukcje zapętlone, ale oba definiują je w kategoriach rekurencji (i przynajmniej w Schemacie doczęsto są implementowane jako makro, które rozwija się w wywołania rekurencyjne). Podobnie, w odpowiedzi Johana nic nie mówi kompilator musi wyemitować zestaw opisany przez Johna do rekurencji. W rzeczy samej,dokładnie ten sam zestaw, niezależnie od tego, czy używasz pętli, czy rekurencji. Kompilator byłby (w pewnym stopniu) zobowiązany do emitowania asemblera, tak jak to opisuje Johan, gdy robisz coś, czego nie da się wyrazić za pomocą pętli. Jak opisano w pracy Steele i wykazano w praktyce języków takich jak Haskell, Scheme i SML, nie jest „wyjątkowo rzadkie”, że wezwania do ogona można „zoptymalizować”, zawsze mogąbyć „zoptymalizowanym”. To, czy określone użycie rekurencji będzie działało w stałej przestrzeni, zależy od tego, jak jest napisane, ale ograniczenia, które musisz zastosować, aby to umożliwić, to ograniczenia, których potrzebujesz, aby dopasować swój problem do kształtu pętli. (W rzeczywistości są one mniej rygorystyczne. Występują problemy, takie jak kodowanie automatów stanów, które są czystsze i wydajniej obsługiwane za pomocą wywołań typu tail, w przeciwieństwie do pętli, które wymagałyby zmiennych pomocniczych.) Ponownie, jedyna rekurencja wymaga więcej pracy kiedy twój kod i tak nie jest pętlą.
Domyślam się, że Johan odnosi się do kompilatorów C, które mają arbitralne ograniczenia, kiedy wykona „optymalizację” wywołania końcowego. Johan prawdopodobnie odnosi się również do języków takich jak C ++ i Rust, kiedy mówi o „językach z typami zarządzanymi”. RAII idiom z C ++ i obecny w Rust, a także sprawia, że rzeczy, które pozornie wyglądają jak rekurencja ogonowa, nie rekurencja ogonowa (bo „destruktorów” nadal trzeba nazwać). Pojawiły się propozycje zastosowania innej składni, aby włączyć nieco inną semantykę, która umożliwiałaby rekurencję ogona (a mianowicie niszczyciele wywołań przedostatnie wywołanie ogona i oczywiście nie zezwalają na dostęp do „zniszczonych” obiektów). (Odśmiecanie nie ma takiego problemu, a wszystkie Haskell, SML i Scheme to języki odśmiecane.) W zupełnie innym stylu niektóre języki, takie jak Smalltalk, ujawniają „stos” jako obiekt pierwszej klasy, w tych przypadki „stos” nie jest już szczegółem implementacji, chociaż nie wyklucza to posiadania osobnych typów wywołań o różnej semantyce. (Java twierdzi, że tak nie jest ze względu na sposób, w jaki obsługuje niektóre aspekty bezpieczeństwa, ale tak naprawdę jest to nieprawda ).
W praktyce częstość niedziałających implementacji wywołań funkcji wynika z trzech głównych czynników. Po pierwsze, wiele języków dziedziczy zepsutą implementację po języku implementacji (zwykle C). Po drugie, deterministyczne zarządzanie zasobami jest przyjemne i sprawia, że problem jest bardziej skomplikowany, chociaż oferuje to tylko garstka języków. Po trzecie, i z mojego doświadczenia wynika, że większość ludzi obchodzi to, że chcą ślady stosu, gdy wystąpią błędy do celów debugowania. Tylko drugi powód może być potencjalnie motywowany teoretycznie.