Gibt es Probleme, die nicht geschrieben werden kann mit tail-Rekursion?

Tail-Rekursion ist ein wichtiger performance-Optimierung stragegy in funktionalen Sprachen, denn es erlaubt rekursive Aufrufe verbrauchen Konstante stack (anstatt O(n)).

Gibt es irgendwelche Probleme, die einfach nicht geschrieben werden kann in eine tail-rekursive Stil, oder ist es immer möglich, zu konvertieren, eine naiv-rekursive Funktion in eine tail-rekursive einer?

Wenn das so ist, eines Tages möglicherweise funktional-Compiler und-Interpreter intelligent genug, um die Konvertierung automatisch?

  • Ich bin nicht einverstanden, dass tail recursion ist ein performance-Optimierung. Es hat zu tun mit der Richtigkeit: Programmierung in einer Sprache ohne dies verhindert, dass Sie von der Behandlung der unbegrenzten Wiederholung mit Rekursion, in der Erwägung, dass in Sprachen mit dieser Funktion, Sie sind frei, verwenden Sie die Rekursion (mit gewissen Einschränkungen) für unbegrenzte Wiederholung. Dies ist ein wichtiger Punkt: Die (Garantie -) Vorhandensein von tail-Rekursion ändert sich die Semantik der Sprache.
  • Wie ändert sich die Semantik? Die gleiche abstrakte Berechnung ist beschrieben in jedem Fall. Die zeitliche und räumliche Komplexität der resultierende code ist wohl eine Implementierung detail, wenn auch ein wichtiger, wenn Sie erwarten, um wirklich das Programm ausführen.
  • Ich sollte vielleicht qualifiziert haben, dass es Veränderungen der Semantik, wenn Sie eine statische Stapel, die ich verstehen ist Normalfall, z.B. mit Java können Sie übergeben Sie einen Parameter beim Start der jvm, wie groß der stack sein soll, aber der Stapel kann nicht wachsen und wachsen, bis die Maschine die Speicher aufgebraucht ist. Sie sprechen von der abstrakten Berechnung, und Sie sind in einem gewissen Sinne richtig, aber dies ist ein klassisches Beispiel einer "leaky abstraction": Das zugrunde liegende Implementierung übt sich, und ohne eine Garantie für tail-calls, die der Programmierer kann sich auf Sie verlassen.
InformationsquelleAutor ctford | 2009-12-11
  1. 47

    Ja, eigentlich ist Sie kann nehmen einige code und konvertieren jedem Aufruf und jeder Rückkehr in eine tail-call. Was Sie am Ende mit ist sogenannte continuation-passing-style, oder CPS.

    Zum Beispiel, hier ist eine Funktion, die zwei rekursive Aufrufe:

    (define (count-tree t)
  (if (pair? t)
    (+ (count-tree (car t)) (count-tree (cdr t)))
    1))

    Und hier ist, wie es Aussehen würde, wenn Sie konvertiert diese Funktion auf eine continuation-passing-style:

    (define (count-tree-cps t ctn)
  (if (pair? t)
    (count-tree-cps (car t)
                    (lambda (L) (count-tree-cps (cdr t)
                                                (lambda (R) (ctn (+ L R))))))
    (ctn 1)))

    Dem zusätzlichen argument, ctn ist eine Prozedur, die count-tree-cps tail-calls anstatt. (sdcvvc Antwort sagt, dass Sie können nicht alles tun, was in O(1) Speicherplatz, und das ist richtig; dabei wird jede Fortsetzung ist ein closure, das braucht etwas Speicher).

    Wusste ich nicht, transformieren Sie die Aufrufe car oder cdr oder + in tail-calls. Das könnte auch getan werden, aber ich nehme an, diejenigen, Blatt aufruft, wäre tatsächlich inlined.

    Nun zum spaßigen Teil. Chicken Scheme tatsächlich diese Umwandlung auf alle code kompiliert. Verfahren zusammengestellt von Huhn nie wieder. Es ist ein klassisches Papier, die erklärt, warum Hühner-Schema bedeutet dies, geschrieben im Jahre 1994 vor dem Huhn wurde umgesetzt: NACHTEILE: sollte nicht die Nachteile, die seine Argumente, Teil II: Cheney auf dem M. T. A.

    Überraschend genug, continuation-passing-style ist ziemlich Häufig in JavaScript. Sie können es verwenden,zu lange andauernde Berechnung, die Vermeidung der browser "langsames Skript" popup. Und es ist attraktiv für asynchrone APIs. jQuery.get (ein einfacher wrapper um XMLHttpRequest) ist eindeutig in continuation-passing-style; das Letzte argument ist eine Funktion.

    • Ich weiß nicht, ob das war die beste Antwort auf die Frage, aber es war mit Abstand die informativste Antwort. +1
    • Es ist einfacher, zu denken, zu transformieren, eine Sprache, die mit springen und keine Prozedur-Aufrufe in einer nur mit tail-rekursive Aufrufe: d.h. jede goto, neben der ersten, wird ein Prozedur-Aufruf, gefolgt von einer Ende. Es ist die Verwandlung, die hinter Dijkstra " GOTO considered harmful.
    • Sollte nicht count-tree-cps enthalten geschachtelte Aufrufe zu sich selbst, anstatt count-tree?
    • Yep. Behoben. . . .
    • Sie können bitte werfen Sie einen Blick auf meine Frage?
    InformationsquelleAutor Jason Orendorff
  2. 26

    Es ist wahr, aber nicht hilfreich, zu beachten, dass jede Sammlung von wechselseitig rekursiven Funktionen, die sich in eine tail-rekursive Funktion. Diese Beobachtung ist auf einer Stufe mit den alten Kastanien her den 1960er Jahren, die control-flow-Konstrukte beseitigt werden könnte, da jedes Programm geschrieben werden kann, wie eine Schleife mit einer case-Anweisung verschachtelte innerhalb.

    Was nützlich zu wissen ist, dass viele Funktionen, die nicht offensichtlich tail-rekursive umgewandelt werden können, um tail-rekursive form durch die Zugabe von akkumulierende Parameter. (Eine extreme version dieser transformation ist die transformation auf eine continuation-passing-style (CPS), aber die meisten Programmierer finden, die die Ausgabe der CPS-Transformation schwer zu Lesen.)

    Hier ist ein Beispiel für eine Funktion, die "rekursive" (eigentlich ist es nur Durchlaufen), aber nicht tail-rekursiv:

    factorial n = if n == 0 then 1 else n * factorial (n-1)

    In diesem Fall mehrfach passiert nach des rekursiven Aufrufs.
    Wir erstellen eine version, die ist tail-rekursiv, indem Sie das Produkt in eine akkumulierende parameter:

    factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

    Die innere Funktion f ist tail-rekursive und kompiliert in einer engen Schleife.

    Finde ich folgende Unterscheidungen hilfreich:

    • In einem iterativen oder rekursiven Programm, Sie lösen ein problem der Größe n durch
      erste Lösung eine subproblem der Größe n-1. Computing-die Fakultät-Funktion
      in diese Kategorie fällt, und es kann getan werden, entweder iterativ oder
      rekursiv. (Diese Idee verallgemeinert, z.B., um die Fibonacci-Funktion, wo
      Sie brauchen beide n-1 und n-2 zu lösen n.)

    • In einem rekursiven Programm, das Sie lösen ein problem der Größe n durch die erste Lösung zwei
      Teilprobleme der Größe n/2. Oder, mehr im Allgemeinen, Sie lösen ein problem der Größe n
      durch die erste Lösung ist, ein subproblem von Größe k und einer Größe n-k, wo 1 < k <
      n      . Quicksort und mergesort sind zwei Beispiele für diese Art von problem, die
      kann leicht programmiert werden, die rekursiv, aber nicht so einfach zu Programmieren
      iterativ oder mit nur tail-Rekursion. (Sie müssen im wesentlichen simulieren Sie die Rekursion in eine explizite
      stack.)

    • In der dynamischen Programmierung lösen Sie ein problem der Größe n durch die erste Lösung alle
      Teilproblemen in allen Größen k, wo k<n. Das finden der kürzesten route von einem
      Punkt zu einem anderen auf die Londoner U-Bahn ist ein Beispiel für diese Art von
      problem. (Die Londoner U-Bahn ist ein mehrfach zusammenhš angender graph, und Sie
      lösen Sie das problem, indem Sie zuerst das Auffinden aller Punkte, für die der kürzeste Pfad
      ist 1 stop, dann für die der kürzeste Pfad ist 2 Haltestellen, etc, etc.)

    Nur die erste Art von Programm hat eine einfach transformation in tail-rekursive form.

    • einige run-time-Umgebungen sehr begrenzten stack-Speicher und unbegrenzte heap-Speicher, also ja, es ist nützlich zu wissen, wie konvertieren von beliebigen code auf tail-rekursive code.
    • Sie können bitte werfen Sie einen Blick auf meine Frage?
    InformationsquelleAutor Norman Ramsey
  3. 11

    Jeder rekursive Algorithmus kann umgeschrieben werden als ein iterativer Algorithmus (vielleicht die einen Stapel oder Liste) und iterative algorithmen kann immer geschrieben werden als tail-rekursive algorithmen, so dass ich denke, es ist wahr, dass jede rekursive Lösung kann irgendwie konvertiert werden, um eine tail-rekursive Lösung.

    (In den Kommentaren, Pascal Cuoq weist darauf hin, dass jeder Algorithmus umgewandelt werden können, um continuation-passing-style.)

    Beachten Sie, dass, nur weil etwas ist tail-rekursiv ist, bedeutet nicht, dass die Speichernutzung ist konstant. Es bedeutet nur, dass der call-return-Stapel wächst nicht.

    • -1: Nicht alle rekursiven Methoden gemacht werden können, tail-rekursiv. Siehe meine Antwort für ein Beispiel.
    • Schreiben Sie eine iterative-tree-traversal Algorithmus durch die Verwendung eines stack.
    • Ich meinte, Sie verbrauchen konstant stack. Vielen Dank für den Hinweis auf meine Fehler.
    • S: "im CPS [...] jeder Anruf ist ein tail call". Finden Sie es für sich selbst in den Kontext: en.wikipedia.org/wiki/Continuation-passing_style
    • Ein rekursiver Algorithmus kann tail-Aufrufe nur, wenn der stack-Werte sind nie geschrieben oder nochmal Lesen, nach ein rekursiver Aufruf, d.h. wenn die bisherigen Werte verworfen werden kann. Wenn nicht, Schwanz Anrufe können nicht verwendet werden.
    • +1 zu stornieren Ben s -1, die ich denke, ist nicht richtig.
    • S: tut mir Leid, aber du bist Antwort ist falsch. Tail-rekursive Baum-traversal und einfügen ist leicht zu schreiben, mit der Fortsetzung vorbei. Finden Sie unter den folgenden urls: stackoverflow.com/questions/833180/handy-f-snippets/... und fortysix-and-two.blogspot.com/2009/06/...

    InformationsquelleAutor
  4. 9

    Können Sie nicht alles tun, was in O(1) Weltraum (space-Hierarchie theorem). Wenn Sie darauf bestehen, tail recursion, dann speichern Sie den call-stack als eines der Argumente. Offensichtlich dadurch ändert sich nichts; irgendwo intern, es ist ein call-stack, du bist einfach so dass es explizit sichtbar.

    Wenn das so ist, eines Tages möglicherweise funktional-Compiler und-Interpreter intelligent genug, um die Konvertierung automatisch?

    Solche Umwandlung wird sich nicht verringern, räumliche Komplexität.

    Als Pascal Cuoq, kommentiert ein anderer Weg ist CPS; alle Anrufe sind tail-rekursive dann.

    InformationsquelleAutor sdcvvc
  5. 1

    Ich glaube nicht, dass so etwas wie tak umgesetzt werden könnte, nur mithilfe von tail calls. (nicht erlaubt Fortsetzungen)

    InformationsquelleAutor recursive
Schreibe einen Kommentar