Uczyłem się F # i zaczyna to wpływać na to, jak myślę, kiedy programuję w C #. W tym celu używam rekurencji, gdy czuję, że wynik poprawia czytelność i nie mogę sobie wyobrazić, że kończy się przepełnieniem stosu.
To prowadzi mnie do pytania, czy kompilatory mogą automatycznie konwertować funkcje rekurencyjne na równoważne formy nierekurencyjne?
programming-languages
compiler
recursion
Aaron Anodide
źródło
źródło
return recursecall(args);
do rekurencji, bardziej złożone rzeczy są możliwe, tworząc wyraźny stos i likwidując go, ale wątpię, że tak będzieOdpowiedzi:
Tak, niektóre języki i kompilatory przekonwertują logikę rekurencyjną na logikę nierekurencyjną. Jest to znane jako optymalizacja połączeń ogonowych - pamiętaj, że nie wszystkie połączenia rekurencyjne są zoptymalizowane. W tej sytuacji kompilator rozpoznaje funkcję formularza:
Tutaj język jest w stanie rozpoznać, że zwracany wynik jest wynikiem innej funkcji i zmienić wywołanie funkcji z nową ramką stosu na skok.
Zrozum, że klasyczna metoda czynnikowa:
nie jest optymalizowany na podstawie ogona ze względu na kontrolę konieczną po powrocie.
Aby zoptymalizować to połączenie z ogonem,
Kompilowanie tego kodu za pomocą
gcc -O2 -S fact.c
(-O2 jest konieczne, aby umożliwić optymalizację w kompilatorze, ale przy większej optymalizacji -O3 trudno jest odczytać człowiekowi ...)Widać w segmencie
.L4
,jne
a nie wcall
(który wywołuje podprogram z nową ramką stosu).Należy pamiętać, że zostało to wykonane w C. Optymalizacja wywołania ogona w Javie jest trudna i zależy od implementacji JVM - rekurencja tail + java i rekursja tail + optymalizacja to dobre zestawy znaczników do przeglądania. Można znaleźć inne języki JVM są w stanie optymalizować rekursji ogonowej lepiej (Clojure try (co wymaga ponownie wystąpi zadzwonić ogon Optimize) lub Scala).
źródło
Stąpaj ostrożnie.
Odpowiedź brzmi: tak, ale nie zawsze i nie wszystkie. Jest to technika, która nosi kilka różnych nazw, ale można znaleźć tu dość definitywne informacje tutaj i na Wikipedii .
Wolę nazwę „Tail Call Optimization”, ale są też inni, a niektórzy mylą to określenie.
To powiedziawszy, jest kilka ważnych rzeczy do zrealizowania:
Aby zoptymalizować ogon, ogon wymaga parametrów, które są znane w momencie nawiązywania połączenia. Oznacza to, że jeśli jeden z parametrów jest wywołaniem samej funkcji, nie można jej przekształcić w pętlę, ponieważ wymagałoby to dowolnego zagnieżdżenia tej pętli, której nie można rozwinąć w czasie kompilacji.
C # nie niezawodnie optymalizuje wezwania ogona. IL ma instrukcję, aby to zrobić, którą wyemituje kompilator F #, ale kompilator C # wyemituje go niekonsekwentnie, aw zależności od sytuacji JIT, JIT może, ale nie musi, wcale. Wszystko wskazuje na to, że nie powinieneś polegać na optymalizacji połączeń ogonowych w języku C #, ryzyko przepełnienia jest znaczne i realne
źródło