Im Kursleiter-Scala-Tutorial verwenden die meisten Beispiele Top-Down-Iterationen. Teilweise, wie ich sehen kann, werden Iterationen verwendet, um for / while-Schleifen zu vermeiden. Ich komme aus C ++ und fühle mich ein wenig verwirrt.
Wird Iteration für / while-Schleifen gewählt? Ist es in der Produktion praktisch? Irgendein Risiko des stackoverflow? Wie steht es mit Effizienz? Wie wäre es mit der Bottom-Up-Dynamic-Programmierung (besonders wenn es sich nicht um eine Tail-Recusion handelt)?
Soll ich weniger "if" -Bedingungen verwenden, stattdessen mehr "case" und Unterklassen?
Wirklich hochwertige Scala wird sehr wenig Iteration und nur etwas mehr Rekursion verwenden. Was mit Schleifen in untergeordneten Imperativsprachen gemacht werden sollte, wird normalerweise am besten mit den Kombinatoren höherer Ordnung durchgeführt, insbesondere mit map und flatmap, aber auch filter, zip, fold, foreach, reduzieren, sammeln, partitionieren, scannen, groupBy und a gute paar andere. Iteration wird am besten nur in leistungskritischen Abschnitten durchgeführt, und Rekursion nur in einigen Fällen, in denen die Kombinatoren höherer Ordnung nicht ganz passen (was normalerweise nicht Tail rekursiv ist, fwiw). In drei Jahren Scala-Codierung in Produktionssystemen verwendete ich Iteration einmal, Rekursion zweimal und Karte ungefähr fünfmal pro Tag.
Hmm, mehrere Fragen in einem.
Ein klassisches Beispiel ist das Schreiben einer Funktion zum Zurückgeben der n-ten Fibonacci-Nummer . Hier ist eine naive rekursive Implementierung:
%Vor%Nun, das ist ineffizient (definitiv nicht tail rekursiv), aber es ist sehr offensichtlich, wie sich seine Struktur auf die Fibonacci-Sequenz bezieht. Wir können es aber richtig rekursiv machen:
%Vor%Das hätte kürzer geschrieben werden können, aber es ist eine effiziente rekursive Implementierung. Das heißt, es ist nicht so schön wie das erste und seine Struktur ist weniger eindeutig auf das ursprüngliche Problem bezogen.
Endlich, schamlos gestohlen von woanders auf dieser Seite ist Luigi Plinges Stream-basierte Implementierung:
%Vor% Sehr knapp, effizient, elegant und (wenn Sie Streams und faule Bewertung verstehen) sehr ausdrucksvoll. Es ist auch rekursiv; #:: ist eine rekursive Funktion, aber eine, die in einem lazy-evaluated Kontext arbeitet. Sie müssen sicherlich in der Lage sein, rekursiv zu denken, um diese Art von Lösung zu finden.
Ich gehe davon aus, dass Sie hier den traditionellen C-Style für meinen.
Rekursive Lösungen können oft while -Schleifen vorgezogen werden, weil C / C ++ / Java-ähnliche while-Schleifen keinen Wert zurückgeben und Nebenwirkungen erfordern, um irgendetwas zu erreichen (dies gilt auch für C-Style) für und Java-style foreach ). Ehrlich gesagt wünschte ich mir oft, Scala hätte while nie umgesetzt (oder es als syntaktischen Zucker für so etwas wie Schemes Namens Let implementiert), weil es klassisch ausgebildeten Java-Entwicklern erlaubt, die Dinge so zu tun, wie sie es immer taten . Da sind Situationen, in denen eine Schleife mit Nebeneffekten, die während Ihnen gibt, eine expressivere Art ist etwas zu erreichen, aber ich hatte eher Java-fixierte Devs gezwungen etwas härter dafür (zB durch Missbrauch eines zum Verständnis ).
Einfach, traditionelle während und für macht clunky imperative Codierung viel zu einfach. Wenn Sie sich nicht darum kümmern, warum benutzen Sie Scala?
Die Tail-Optimierung eliminiert das Risiko von Stackoverflow. Wenn Sie rekursive Lösungen rekursiv rekursiv schreiben, können sie sehr hässlich werden (insbesondere in jeder Sprache, die auf der JVM ausgeführt wird).
Rekursive Lösungen können effizienter sein als zwingendere Lösungen, manchmal überraschend. Ein Grund ist, dass sie oft auf Listen operieren, und zwar nur auf Kopf und Tail Zugriff. Kopf- und Fußzeilenoperationen in Listen sind tatsächlich schneller als Operationen mit wahlfreiem Zugriff in strukturierteren Sammlungen.
Ein guter rekursiver Algorithmus reduziert typischerweise ein komplexes Problem auf eine kleine Menge einfacherer Probleme, wählt einen zu lösenden aus und delegiert den Rest an eine andere Funktion (normalerweise ein rekursiver Aufruf an sich selbst). Nun, für mich hört sich das nach einer guten Eignung für dynamische Programmierung an. Sicher, wenn ich einen rekursiven Ansatz für ein Problem versuche, beginne ich oft mit einer naiven Lösung, von der ich weiß, dass sie nicht jeden Fall lösen kann, wo sie fehlschlägt, dieses Muster zur Lösung hinzufügt und zum Erfolg iteriert.
The Little Schemer hat viele Beispiele dieses iterativen Ansatzes für die rekursive Programmierung, insbesondere weil es re - verwendet frühere Lösungen als Unterkomponenten für spätere, komplexere. Ich würde sagen, es ist der Inbegriff des Ansatzes der dynamischen Programmierung. (Es ist auch eines der am besten geschriebenen Lehrbücher über Software, die jemals produziert wurden). Ich kann es empfehlen, nicht zuletzt weil es dir Scheme zur gleichen Zeit beibringt. Wenn Sie Scheme nicht wirklich lernen wollen (warum? Warum nicht?), Wurde es für einige andere angepasst Sprachen
if Ausdrücke in Scala geben Werte zurück (was sehr nützlich ist und warum Scala keinen ternären Operator benötigt). Es gibt keinen Grund, einfach zu vermeiden
%Vor%Ausdrücke.Der Hauptgrund für die Übereinstimmung anstelle einer einfachen if ... else besteht darin, die Möglichkeiten von case-Anweisungen zu nutzen, um Informationen aus komplexen Objekten zu extrahieren. Hier ist ein Beispiel.
Auf der anderen Seite ist if ... else if ... else if ... else ein schreckliches Muster
Wo immer Sie finden, dass Sie sonst, wenn geschrieben haben, suchen Sie nach einer Alternative. match ist ein guter Anfang.
Ich gehe davon aus, dass Sie in Ihrer Frage "Rekursion" meinen, weil Sie "Rekursion" sagen, und nicht "Iteration" (die nicht für "over / while loops" gewählt werden kann) iterativ: D).
Vielleicht interessiert es Sie, Effective Scala zu lesen, insbesondere den Abschnitt über Kontrollstrukturen, der meist Ihre Frage beantworten sollte. Kurz gesagt:
Rekursion ist nicht "besser" als Iteration. Oft ist es einfacher, einen rekursiven Algorithmus für ein gegebenes Problem zu schreiben, dann einen iterativen Algorithmus zu schreiben (natürlich gibt es Fälle, in denen das Gegenteil zutrifft). Wenn "Tail Call Optimization" auf ein Problem angewendet werden kann, konvertiert der Compiler es tatsächlich in einen iterativen Algorithmus, was es unmöglich macht, dass ein StackOverflow ohne Leistungseinbußen auftritt. In Effective Scala können Sie auch über die Tail-Call-Optimierung lesen.
Das Hauptproblem Ihrer Frage ist, dass sie sehr ist. Es gibt viele verfügbare Ressourcen für funktionale Programmierung, idiomatische Scala, dynamische Programmierung und so weiter und keine Antwort hier auf Stack Overflow wäre in der Lage, alle diese Themen zu behandeln. Es wäre wahrscheinlich eine gute Idee, die Interwebs eine Weile zu durchstreifen und dann mit konkreteren Fragen zurückzukommen :)
Einer der Hauptvorteile der Rekursion besteht darin, dass Sie Lösungen ohne Mutation erstellen können. Für folgendes Beispiel müssen Sie die Summe aller Elemente einer Liste berechnen.
Einer der vielen Wege, dieses Problem zu lösen, ist wie folgt. Die imperative Lösung für dieses Problem verwendet For-Schleife wie folgt:
%Vor%Und Rekursionslösung würde folgendermaßen aussehen:
%Vor%Der Unterschied besteht darin, dass eine rekursive Lösung keine veränderbaren temporären Variablen verwendet, indem Sie das Problem in kleinere Teile aufteilen. Da es bei der funktionalen Programmierung nur darum geht, side-effect-freie Programme zu schreiben, ist es immer ratsam, Rekursion vs Schleifen (die mutierende Variablen verwenden) zu verwenden.
Die Kopfrekursion ist eine traditionelle Methode der Rekursion, bei der Sie zuerst den rekursiven Aufruf durchführen und dann den Rückgabewert von der rekursiven Funktion übernehmen und das Ergebnis berechnen.
Im Allgemeinen wird beim Aufruf einer Funktion ein Eintrag zum Aufruf-Stack eines aktuell laufenden Threads hinzugefügt. Der Nachteil ist, dass der Aufrufstapel eine definierte Größe hat, so dass Sie die StackOverflowError-Ausnahme schnell erhalten können. Deshalb zieht Java es vor, eher zu iterieren als zu rekurrieren. Da Scala auf der JVM läuft, leidet auch Scala an diesem Problem. Aber mit Scala 2.8.1 beginnt Scala diese Einschränkung durch die Tail Call Optimierung. Sie können eine Tail-Rekursion in Scala durchführen.
Rekapitulation ist der bevorzugte Weg in der funktionalen Programmierung, um die Verwendung von Mutationen zu vermeiden und zweitens wird die Tail-Rekursion in Scala unterstützt, so dass Sie nicht in StackOverFlow-Exceptions gelangen, die Sie in Java erhalten.
Hoffe, das hilft.
Was den Stack-Überlauf anbelangt, so können Sie oft mit der Beseitigung von Tail Calls davonkommen.
Der Grund, warum scala und andere Funktionsparadigmen Schleifen für / while vermeiden, hängt stark von Zustand und Zeit ab. Das macht es viel schwieriger, über komplexe "Schleifen" in einem formalen und präzisen Manuskript nachzudenken.
Tags und Links scala functional-programming recursion