Czy i czy kompilatory mogą konwertować logikę rekurencyjną na równoważną logikę nierekurencyjną?

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?

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:

int foo(n) {
  ...
  return bar(n);
}

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:

int factorial(n) {
  if(n == 0) return 1;
  if(n == 1) return 1;
  return n * factorial(n - 1);
}

nie jest optymalizowany na podstawie ogona ze względu na kontrolę konieczną po powrocie.

Aby zoptymalizować to połączenie z ogonem,

int _fact(int n, int acc) {
    if(n == 1) return acc;
    return _fact(n - 1, acc * n);
}

int factorial(int n) {
    if(n == 0) return 1;
    return _fact(n, 1);
}

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 ...)

_fact:
.LFB0:
        .cfi_startproc
        cmpl    $1, %edi
        movl    %esi, %eax
        je      .L2
        .p2align 4,,10
        .p2align 3
.L4:
        imull   %edi, %eax
        subl    $1, %edi
        cmpl    $1, %edi
        jne     .L4
.L2:
        rep
        ret
        .cfi_endproc

Widać w segmencie .L4, jnea nie w call(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).

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