Frage zum „Schwanz Call-Optimierung“ Artikel

Question

Ich habe eine Frage bezüglich dieser Artikel.

Zwischen diesem Code

function odds(n, p) {
  if(n == 0) {
    return 1
  } else {
    return (n / p) * odds(n - 1, p - 1)
  }
}

und dieser Code

(function(){
  var odds1 = function(n, p, acc) {
    if(n == 0) {
      return acc
    } else {
      return odds1(n - 1, p - 1, (n / p) * acc)
    }
  }

  odds = function(n, p) {
    return odds1(n, p, 1)
  }  
})()

1) Ich bin verwirrt darüber, wie viel, das hilft. Hat der zweite Schnipsel einfach einen Endrekursion haben, die weniger Overhead erzeugt, weil er berechnet, was es braucht, bevor er sich selbst aufruft wieder, oder gibt es etwas mehr fehlt mir?

Wie ich es verstehe, noch der Schwanz Anruf nicht beseitigt, nur optimiert.

2) Und warum es notwendig odds und odds1 sowieso sein? Es ist noch nicht entweder mir klar.

Answer 1

Ich bin verwirrt darüber, wie viel, das hilft. Hat der zweite Schnipsel einfach einen Endrekursion haben, die weniger Overhead erzeugt, weil er berechnet, was es braucht, bevor er sich selbst aufruft wieder, oder gibt es etwas mehr fehlt mir?

Wie ich es verstehe, noch der Schwanz Anruf nicht beseitigt, nur optimiert.

Wenn das Ende einer Prozedur sieht wie folgt aus:

push args
call foo
return

Dann kann der Compiler die Optimierung weg nur

jump startOfFoo

Die Beseitigung der Prozeduraufruf vollständig.

Und warum braucht es Chancen und odds1 sowieso sein? Es ist noch nicht entweder mir klar.

Der „Vertrag“ von odds gibt an nur zwei Argumenten - das dritte Argument ist nur eine Implementierung Detail. So Sie, dass sie in einem internen Verfahren zu verbergen, und einen „Wrapper“, wie die externe API präsentieren.

Sie könnten odds1 etwas wie oddsImpl nennen und es wäre es klarer machen, denke ich.

Answer 2

Die erste Version ist nicht Schwanz rekursive weil nach dem Wert von odds(n - 1, p - 1) bekommen es muss dann multiplizieren sie durch (n / p), dies in die Berechnung der Parameter für die odds1 Funktion, um es richtig Schwanz rekursiv zu machen.

bewegt sich die zweite Version

Wenn Sie auf den Call-Stack sehen dann die erste so gehen würde:

odds(2, 3)
  odds(1, 2)
    odds(0, 1)
    return 1
  return 1/2 * 1
return 2/3 * 1/2

, während die zweite wäre:

odds(2, 3)
  odds1(2, 3, 1)
    odds1(1, 2, 2/3)
      odds1(0, 1, 1/2 * 2/3)
      return 1/3
    return 1/3
  return 1/3
return 1/3

, weil Sie einfach den Wert des rekursiven Aufruf Rückkehr der Compiler dies leicht optimieren können:

odds(2, 3)
#discard stackframe
odds1(2, 3, 1)
#discard stackframe
odds1(1, 2, 2/3)
#discard stackframe
odds1(0, 1, 1/3)
return 1/3

Der Grund für odds und odds1 ist einfach die anfängliche Akkumulatorwert zu liefern, wenn ein anderer Code diese Funktion aufruft.

Answer 3

Die Optimierung der Endrekursion wird folgt wie im ersten Beispiel, da Sie nicht das Ergebnis der Multiplikation return (n / p) * odds(n - 1, p - 1) berechnen können, bis Sie die Quoten genannt habe (n-1), die interperator hat unsere aktuelle Position im Speicher zu halten (auf der Stapel), und öffnen Sie einen neuen Anruf Quoten.

Recursively, das wird auch in dem nächsten Anruf passieren, und der Computer, nachdem es und so weiter. So wir n Operationen, die von der Zeit haben anhängig erreichen wir das Ende unserer Rekursion und starten Sie die valuesand Rücksendung der Produkte berechnet wird.

Im zweiten Beispiel, da die Return-Anweisung einfach ausgeführt ist return odds1(n - 1, p - 1, (n / p) * acc) wir die Funktionsargumente berechnen können, und rufen Sie einfach die odds1 (n-1) ohne unsere aktuelle Position zu halten . das ist, wo die Optimierung ist, weil ich jetzt darf nicht vergessen, nicht, wo ich jedes Mal, wenn ich auf dem Stapel einen neuen Rahmen zu öffnen bin.

Denken Sie daran, wie Buch Referenzen. Stellen Sie sich ein Kochbuch öffnen und gehen Sie zu einem bestimmten Rezept und die Zutaten sind wie folgt aufgeführt:

1. Salz
2. die Zutaten auf der nächsten Seite

die nächste Seite hat

1. Pfeffer
2. die Zutaten auf der nächsten Seite

usw. wie Sie sagen, was alle Zutaten sind? Sie müssen bedenken, was Sie auf jeder Seite gesehen haben!

obwohl das zweite Beispiel ist eher wie die folgende Zutatenliste:

1. Salz
2. vergessen diese, benutzen Sie einfach, was Sie auf der nächsten Seite

die nächste Seite hat:

1. Salz
2. Pfeffer
3. vergessen diese, benutzen Sie einfach, was Sie auf der nächsten Seite

usw. Mit der Zeit erreichen Sie die letzte Seite (beachten Sie, dass die Analogie genau ist, dass beide die gleiche Menge an Funktionsaufrufe nehmen), Sie haben alle Zutaten, ohne „halten in Erinnerung“, was Sie auf jeder Seite sah, weil es alles, was es auf der letzten Seite!