Scala Neuling: Rekursion und stackoverflow Fehler

Question

Als Scala Neuling, lese ich Bücher, Dokumente und versuchen, Probleme zu lösen gefunden auf http://aperiodic.net/phil/scala/s-99/. Es scheint korrekt zu sein, dass Scala-Code auf unveränderlichen Werten (val) und auf Rekursion basiert und nicht auf Schleifen und Variablen, um die Parallelität sicherer zu machen und die Notwendigkeit zu vermeiden, Sperren zu verwenden.

Zum Beispiel kann eine mögliche Lösung für die Ausübung P22 (http://aperiodic.net/phil/scala/s-99/p22.scala) ist:

// Recursive. 
def rangeRecursive(start: Int, end: Int): List[Int] = 
if (end < start) Nil 
else start :: rangeRecursive(start + 1, end) 

Natürlich ist dieser Code kompakt und sieht smart, aber natürlich, wenn die Anzahl der Rekursion hoch ist, werden Sie einen StackOverflow-Fehler (RangeRecorssive (1.10000) zum Beispiel ohne JVM-Tuning). Wenn Sie sich die Quelle des eingebauten List.range ansehen (https://github.com/scala/scala/blob/v2.9.2/src/library/scala/collection/immutable/List.scala#L1), dann werden Sie Ich sehe, dass Loops und Vars verwendet werden.

Meine Frage ist, wie man den Einfluss des Scala-Lernens, das Vals und Rekursion fördert, in der Kenntnis, dass solcher Code aufgrund der Anzahl der Rekursion brechen kann, verwaltet?

Answer 1

Das Schöne an Scala ist, dass Sie Ihren Weg dorthin einfach finden. Zu Beginn können Sie Schleifen schreiben und mehr mit Rekursion tun, wenn Sie mit der Sprache vertrauter werden. Sie können dies nicht mit den "reineren" funktionalen Sprachen wie Clojure oder Haskell machen. Mit anderen Worten, Sie können sich mit der Unveränderlichkeit und val vertraut machen und später zur Rekursion übergehen.

Wenn Sie mit der Rekursion beginnen, sollten Sie die Tail Call Rekursion nachschlagen. Wenn der rekursive Aufruf der letzte Aufruf in der Funktion ist, wird der Scala-Compiler dies in einer Schleife in Bytecode optimieren. Auf diese Weise erhalten Sie nicht StackOverflowError s. Wenn Sie die Annotation @tailrec Ihrer rekursiven Funktion hinzufügen, warnt Sie der Compiler außerdem, wenn Ihre Funktion nicht rekursiv ist.

Zum Beispiel ist die Funktion in Ihrer Frage nicht Tail Call rekursiv. Es sieht so aus, als ob der Aufruf an rangeRecursive der letzte in der Funktion ist, aber wenn dieser Aufruf zurückkehrt, muss er noch start an das Ergebnis des Aufrufs anhängen. Daher kann es nicht rekursiv sein: Es muss immer noch funktionieren, wenn der Aufruf zurückkehrt.

Answer 2

Wenn Sie das oben beschriebene so umschreiben, dass es rekursiv ist, optimiert der Compiler den Code in eine while-Schleife. Darüber hinaus können Sie die @tailrec Annotation verwenden, um einen Fehler zu erhalten, wenn die Methode, die es notiert, nicht tail rekursiv ist. So können Sie wissen, wann Sie es richtig gemacht haben.

Answer 3

Hier ist ein Beispiel für die rekursive Methode dieser Methode. Die @tailrec Annotation ist nicht notwendig, der Compiler optimiert ohne sie. Aber dadurch wird der Compiler dazu gebracht, einen Fehler zu melden, wenn die Optimierung nicht möglich ist.

scala> def rangeRecursive(start: Int, end: Int): List[Int] = { 
    | @scala.annotation.tailrec 
    | def inner(accum : List[Int], start : Int) : List[Int] = { 
    |  if (end < start) accum.reverse 
    |  else inner(start :: accum, start + 1) 
    | } 
    | 
    | inner(Nil, start) 
    | } 
rangeRecursive: (start: Int,end: Int)List[Int] 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

Es verwendet eine übliche Technik „Akkumulator Übertragungsstil“ genannt, in denen Zwischenergebnisse akkumuliert werden und zum nächsten Schritt in der Rekursion geben. Der unterste Schritt ist verantwortlich für das Zurückgeben des akkumulierten Ergebnisses. In diesem Fall baut der Akkumulator sein Ergebnis rückwärts auf, so dass der Basisfall es umkehren muss. Hier

Answer 4

ist eine Alternative zu James Iry Antwort, mit dem gleichen Verhalten:

def rangeRecursive(start: Int, end: Int): List[Int] = { 
    def inner(start : Int) : Stream[Int] = { 
     if (end < start) Stream.empty 
     else start #:: inner(start + 1) 
    } 

    inner(start).toList 
} 

scala> rangeRecursive(1,10000) 
res1: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,... 

Dies ist keine StackOverflowError weil der Stream.cons -Operator (#::) speichert, die durch Bezugnahme den Schwanz wirft.Mit anderen Worten, die Stream-Elemente werden erst berechnet, wenn stream.toList aufgerufen wird.

Meiner Meinung nach ist dies besser lesbar als das Speichermuster, weil sie am ehesten den naiven ursprünglichen Algorithmus ähnelt (nur :: von #:: und Nil durch Stream.empty ersetzen). Es gibt auch keine Notwendigkeit für accum.reverse, die leicht vergessen werden könnte.