Können und können Compiler rekursive Logik in äquivalente nicht-rekursive Logik konvertieren?

15

Ich habe F # gelernt und es beginnt zu beeinflussen, wie ich denke, wenn ich C # programmiere. Zu diesem Zweck habe ich die Rekursion verwendet, wenn ich der Meinung bin, dass das Ergebnis die Lesbarkeit verbessert, und ich kann mir nicht vorstellen, dass es zu einem Stapelüberlauf führt.

Dies führt mich zu der Frage, ob Compiler rekursive Funktionen automatisch in eine äquivalente nicht-rekursive Form konvertieren könnten oder nicht.

Aaron Anodide
quelle
Endrekursion Optimierung ist ein gutes , wenn einfaches Beispiel , aber das funktioniert nur , wenn Sie return recursecall(args);für die Rekursion, desto komplexer Sachen durch die Schaffung eines expliziten Stapel möglich ist und es auf kurvigen, aber ich bezweifle , werden sie
Ratsche Freak
@ratchet Freak: Rekursion bedeutet nicht "Berechnung, die einen Stapel verwendet".
Giorgio
1
@Giorgio Ich weiß , aber ein Stapel ist der einfachste Weg , Rekursion zu einer Schleife zu konvertieren
Ratsche Freak

Antworten:

21

Ja, einige Sprachen und Compliler konvertieren rekursive Logik in nicht rekursive Logik. Dies wird als Tail-Call-Optimierung bezeichnet. Beachten Sie, dass nicht alle rekursiven Aufrufe für die Tail-Call-Optimierung geeignet sind. In dieser Situation erkennt der Compiler eine Funktion der Form:

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

Hier kann die Sprache erkennen, dass das zurückgegebene Ergebnis das Ergebnis einer anderen Funktion ist, und einen Funktionsaufruf mit einem neuen Stapelrahmen in einen Sprung umwandeln.

Beachten Sie, dass die klassische Fakultätsmethode:

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

ist wegen der bei der rückgabe notwendigen inspektion nicht schwanzrufoptimierbar.

Um diesen Tail Call zu optimieren,

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);
}

Kompilieren Sie diesen Code mit gcc -O2 -S fact.c(-O2 ist erforderlich, um die Optimierung im Compiler zu ermöglichen, aber mit mehr Optimierungen von -O3 wird es für einen Menschen schwer zu lesen ...)

_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

Man kann in dem Segment sehen .L4, die jneeher als ein call(das macht einen Subroutinen - Aufruf mit einem neuen Stapelrahmen).

Beachten Sie, dass dies mit C durchgeführt wurde. Die Optimierung von Tail-Aufrufen in Java ist schwierig und hängt von der JVM-Implementierung ab. Tail-Recursion + Java und Tail-Recursion + Optimierung sind gute Tag-Sets zum Durchsuchen. Sie können andere JVM Sprachen sind in der Lage zu optimieren Endrekursion finden besser (try clojure (die die erfordert recur zu Endrekursion optimize) oder scala).

Gemeinschaft
quelle
1
Ich bin mir nicht sicher, ob das der Fall ist. Nur weil die Laufzeit auf eine bestimmte Weise Stapelspeicher belegt oder nicht belegt, heißt das nicht, dass die Funktion nicht rekursiv ist.
1
@MattFenwick Wie meinst du das? "Dies veranlasst mich zu fragen, ob Compiler rekursive Funktionen automatisch in eine äquivalente nicht-rekursive Form konvertieren könnten oder nicht" - die Antwort lautet "Ja unter bestimmten Bedingungen". Die Bedingungen werden demonstriert, und es gibt einige Fallstricke in bestimmten anderen populären Sprachen mit den von mir erwähnten Optimierungen für den Tail Call.
9

Vorsichtig auftreten.

Die Antwort lautet ja, aber nicht immer und nicht alle. Dies ist eine Technik, die unter ein paar verschiedenen Namen geführt wird, aber hier und auf Wikipedia finden Sie einige ziemlich eindeutige Informationen .

Ich bevorzuge den Namen "Tail Call Optimization", aber es gibt andere und einige Leute werden den Begriff verwirren.

Das heißt, es gibt ein paar wichtige Dinge zu realisieren:

  • Um einen Tail-Anruf zu optimieren, sind für den Tail-Anruf Parameter erforderlich, die zum Zeitpunkt des Anrufs bekannt sind. Das heißt, wenn einer der Parameter ein Aufruf der Funktion selbst ist, kann er nicht in eine Schleife konvertiert werden, da dies eine willkürliche Verschachtelung dieser Schleife erfordern würde, die zur Kompilierungszeit nicht erweitert werden kann.

  • C # optimiert Tail Calls nicht zuverlässig. Die IL verfügt über die Anweisung, die der F # -Compiler ausgibt, der C # -Compiler gibt sie jedoch inkonsistent aus. Abhängig von der JIT-Situation kann die JIT dies möglicherweise tun oder auch gar nicht. Sie sollten sich nicht darauf verlassen, dass Ihre Tail Calls in C # optimiert werden. Das Risiko eines Überlaufs ist dabei erheblich und real

Jimmy Hoffa
quelle
1
Sind Sie sicher, dass die OP dies fragt? Wie ich unter der anderen Antwort geschrieben habe, heißt das nicht, dass die Funktion nicht rekursiv ist, nur weil die Laufzeit auf bestimmte Weise Stapelspeicher belegt oder nicht belegt.
1
@MattFenwick, das ist eigentlich ein großartiger Punkt, in realer Hinsicht kommt es darauf an. Der F # -Compiler, der Tail-Call-Anweisungen ausgibt, behält die rekursive Logik vollständig bei. Wachsende, jedoch andere Compiler können buchstäblich zu einer Schleife kompilieren. (Technisch gesehen kompiliert das JIT zu einer Schleife oder möglicherweise sogar ohne Schleife, wenn die Schleife ganz vorne ist)
Jimmy Hoffa,