Sind funktionale Sprachen rekursiver?

41

TL; DR: Gehen funktionale Sprachen besser mit Rekursion um als nicht funktionale?

Ich lese gerade Code Complete 2. Irgendwann im Buch warnt uns der Autor vor einer Rekursion. Er sagt, dass dies nach Möglichkeit vermieden werden sollte und dass Funktionen mit Rekursion im Allgemeinen weniger effektiv sind als eine Lösung mit Schleifen. Als Beispiel hat der Autor eine Java-Funktion geschrieben, die mithilfe der Rekursion die Fakultät einer Zahl wie dieser berechnet (sie ist möglicherweise nicht genau dieselbe, da ich das Buch momentan nicht bei mir habe):

public int factorial(int x) {
    if (x <= 0)
        return 1;
    else
        return x * factorial(x - 1);
}

Dies wird als schlechte Lösung dargestellt. In funktionalen Sprachen ist die Verwendung von Rekursion jedoch häufig die bevorzugte Methode. Hier ist zum Beispiel die Fakultätsfunktion in Haskell mit Rekursion:

factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * factorial (n - 1)

Und wird allgemein als gute Lösung akzeptiert. Wie ich gesehen habe, verwendet Haskell sehr oft die Rekursion, und ich habe nirgends gesehen, dass sie verpönt ist.

Meine Frage ist also im Grunde:

  • Behandeln funktionale Sprachen Rekursionen besser als nichtfunktionale?

EDIT: Ich bin mir bewusst, dass die Beispiele, die ich verwendet habe, nicht die besten sind, um meine Frage zu veranschaulichen. Ich wollte nur darauf hinweisen, dass Haskell (und funktionale Sprachen im Allgemeinen) Rekursion viel häufiger als nicht funktionale Sprachen verwendet.

Marco-Fiset
quelle
10
Ein typisches Beispiel: In vielen funktionalen Sprachen wird die Tail Call-Optimierung intensiv genutzt, während dies nur in sehr wenigen prozeduralen Sprachen möglich ist. Dies bedeutet, dass die Endanrufrekursion in diesen funktionalen Sprachen viel billiger ist.
Joachim Sauer
7
Tatsächlich ist die von Ihnen angegebene Haskell-Definition ziemlich schlecht. factorial n = product [1..n]ist prägnanter, effizienter und überläuft den Stapel nicht für große n(und wenn Sie Memoisierung benötigen, sind ganz andere Optionen erforderlich). productwird in Bezug auf einige definiert fold, die sich rekursiv definiert, aber mit äußerster Vorsicht. Rekursion ist die meiste Zeit eine akzeptable Lösung, aber es ist immer noch leicht, es falsch / suboptimal zu machen.
1
@JoachimSauer - Mit ein wenig Verschönerung würde Ihr Kommentar eine lohnende Antwort geben.
Mark Booth
Deine Bearbeitung zeigt an, dass du meine Abweichung nicht bemerkt hast. Die von Ihnen angegebene Definition ist ein perfektes Beispiel für eine Rekursion, die selbst in funktionalen Sprachen schlecht ist . Meine Alternative ist auch rekursiv (obwohl sie sich in einer Bibliotheksfunktion befindet) und sehr effizient, nur wie sie rekursiv ist, macht einen Unterschied. Haskell ist auch ein merkwürdiger Fall, in dem Faulheit gegen die üblichen Regeln verstößt (Beispiel: Funktionen können den Stapel überlaufen lassen, während sie rekursiv sind, und sehr effizient sein, ohne rekursiv zu sein).
@delnan: Danke für die Klarstellung! Ich bearbeite meine edit;)
marco-fiset

Antworten:

36

Ja, aber nicht nur, weil sie es können , sondern weil sie es müssen .

Das Schlüsselkonzept hier ist Reinheit : Eine reine Funktion ist eine Funktion ohne Nebenwirkungen und ohne Zustand. In funktionalen Programmiersprachen wird Reinheit im Allgemeinen aus vielen Gründen empfohlen, z. B. aus Gründen, die den Code betreffen, und um nicht offensichtliche Abhängigkeiten zu vermeiden. Einige Sprachen, insbesondere Haskell, erlauben sogar nur reinen Code. Alle Nebenwirkungen, die ein Programm haben kann (z. B. die Ausführung von E / A-Vorgängen), werden in eine nicht reine Laufzeitumgebung verschoben, wodurch die Sprache selbst rein bleibt.

Keine Nebenwirkungen zu haben bedeutet, dass Sie keine Schleifenzähler haben können (da ein Schleifenzähler einen veränderlichen Zustand darstellen würde und das Ändern eines solchen Zustands ein Nebeneffekt wäre). Das iterativste, was eine reine funktionale Sprache erhalten kann, ist das Durchlaufen einer Liste ( Diese Operation wird normalerweise als foreachoder bezeichnet map. Rekursion ist jedoch eine natürliche Entsprechung zur reinen Funktionsprogrammierung - es ist kein Status für die Rekursion erforderlich, außer für die (schreibgeschützten) Funktionsargumente und einen (schreibgeschützten) Rückgabewert.

Das Fehlen von Nebenwirkungen bedeutet jedoch auch, dass die Rekursion effizienter implementiert und vom Compiler aggressiver optimiert werden kann. Ich habe selbst keinen solchen Compiler eingehend untersucht, aber soweit ich weiß, führen die Compiler der meisten funktionalen Programmiersprachen eine Tail-Call-Optimierung durch, und einige kompilieren möglicherweise sogar bestimmte Arten von rekursiven Konstrukten in Schleifen hinter den Kulissen.

tdammers
quelle
2
Für die Aufzeichnung hängt die Tail Call Elimination nicht von der Reinheit ab.
scarfridge
2
@scarfridge: Natürlich nicht. Wenn Reinheit gegeben ist, ist es für einen Compiler jedoch viel einfacher, Ihren Code neu zu ordnen, um Endaufrufe zu ermöglichen.
tdammers
GCC leistet einen viel besseren Job als GHC, da Sie die Gesamtbetriebskosten nicht für die Erstellung eines Thunks leisten können.
Dan_waterworth
18

Sie vergleichen Rekursion mit Iteration. Ohne Tail-Call-Eliminierung ist die Iteration in der Tat effizienter, da es keinen zusätzlichen Funktionsaufruf gibt. Außerdem kann die Iteration für immer weitergehen, während der Stapelspeicher für zu viele Funktionsaufrufe knapp wird.

Für die Iteration muss jedoch ein Zähler geändert werden. Das heißt, es muss eine veränderbare Variable geben , die in einer rein funktionalen Umgebung verboten ist. Daher sind die funktionalen Sprachen so konzipiert, dass sie ohne Iteration ausgeführt werden können, daher die optimierten Funktionsaufrufe.

Aber nichts davon spricht an, warum Ihr Codebeispiel so elegant ist. Ihr Beispiel zeigt eine andere Eigenschaft, nämlich den Mustervergleich . Aus diesem Grund hat das Haskell-Beispiel keine expliziten Bedingungen. Mit anderen Worten, es ist nicht die optimierte Rekursion, die Ihren Code klein macht. es ist die Musterübereinstimmung.

Chrisaycock
quelle
Ich weiß bereits, worum es beim Pattern Matching geht, und ich denke, es ist eine großartige Funktion in Haskell, die ich in den von mir verwendeten Sprachen vermisse!
marco-fiset
@marcof Mein Punkt ist, dass all das Gerede über Rekursion gegen Iteration nicht die Glätte Ihres Codebeispiels anspricht. Es geht wirklich um Mustervergleich gegen Bedingungen. Vielleicht hätte ich das in meiner Antwort erwähnen sollen.
Chrisaycock
Ja, das habe ich auch verstanden: P
marco-fiset
@chrisaycock: Wäre es möglich, die Iteration als Endrekursion zu betrachten, bei der alle im Schleifenkörper verwendeten Variablen sowohl Argumente als auch Rückgabewerte der rekursiven Aufrufe sind?
Giorgio
@ Giorgio: Ja, lassen Sie Ihre Funktion ein Tupel desselben Typs nehmen und zurückgeben.
Ericson2314
5

Technisch nein, aber praktisch ja.

Rekursion ist weitaus häufiger, wenn Sie eine funktionale Herangehensweise an das Problem verfolgen. Daher enthalten Sprachen, die für einen funktionalen Ansatz entwickelt wurden, häufig Funktionen, die die Rekursion einfacher / besser / weniger problematisch machen. Auf den ersten Blick gibt es drei gebräuchliche:

  1. Tail Call-Optimierung. Wie in anderen Postern bereits erwähnt, erfordern funktionale Sprachen häufig TCO.

  2. Lazy Evaluation. Haskell (und einige andere Sprachen) wird faul bewertet. Dies verzögert die eigentliche 'Arbeit' einer Methode, bis sie benötigt wird. Dies führt tendenziell zu rekursiveren Datenstrukturen und rekursiven Methoden zu deren Bearbeitung.

  3. Unveränderlichkeit. Die meisten Dinge, mit denen Sie in funktionalen Programmiersprachen arbeiten, sind unveränderlich. Dies erleichtert die Rekursion, da Sie sich nicht mit dem Zustand von Objekten im Laufe der Zeit befassen müssen. Sie können zum Beispiel keinen Wert unter sich ändern lassen. Viele Sprachen sind auch so konzipiert, dass sie reine Funktionen erkennen . Da reine Funktionen keine Nebenwirkungen haben, hat der Compiler viel mehr Freiheit, in welcher Reihenfolge die Funktionen ausgeführt werden, und andere Optimierungen.

Keines dieser Dinge ist wirklich spezifisch für funktionale Sprachen im Vergleich zu anderen, daher sind sie nicht einfach besser, weil sie funktional sind. Da sie jedoch funktional sind, tendieren die getroffenen Entwurfsentscheidungen zu diesen Funktionen, da sie bei der funktionalen Programmierung nützlicher sind (und ihre Nachteile weniger problematisch sind).

Telastyn
quelle
1
Betreff: 1. Frühe Retouren haben nichts mit Tail Calls zu tun. Sie können mit einem Tail-Aufruf frühzeitig zurückkehren und die "späte" Rückkehr auch mit einem Tail-Aufruf versehen und Sie können einen einzelnen einfachen Ausdruck haben, bei dem sich der rekursive Aufruf nicht in einer Tail-Position befindet (vgl. Die Fakultätsdefinition von OP).
@delnan: Danke; Es ist früh und es ist schon eine Weile her, seit ich das Ding studiert habe.
Telastyn
1

Haskell und andere funktionale Sprachen verwenden im Allgemeinen eine verzögerte Auswertung. Mit dieser Funktion können Sie nicht endende rekursive Funktionen schreiben.

Wenn Sie eine rekursive Funktion schreiben, ohne einen Basisfall zu definieren, in dem die Rekursion endet, erhalten Sie unendlich viele Aufrufe dieser Funktion und einen Stapelüberlauf.

Haskell unterstützt auch Optimierungen für rekursive Funktionsaufrufe. In Java würde sich jeder Funktionsaufruf stapeln und Overhead verursachen.

Also ja, funktionale Sprachen können besser mit Rekursion umgehen als andere.

Mert Akcakaya
quelle
5
Haskell gehört zu den wenigen nicht-strengen Sprachen - die gesamte ML - Familie (abgesehen von einigen Forschungs Spin - offs , die hinzufügen Faulheit), alle gängigen Lisps, Erlang, etc. sind alle streng. Auch scheinen die Absätze aus - wie Sie richtig im ersten Absatz angeben, Faulheit nicht erlaubt unendliche Rekursion (der Haskell Auftakt die immens nützlich ist forever a = a >> forever azum Beispiel).
@deinan: Soweit ich weiß, bietet SML / NJ auch eine verzögerte Auswertung, ist aber eine Ergänzung zu SML. Ich wollte auch zwei der wenigen faulen funktionalen Sprachen nennen: Miranda und Clean.
Giorgio
1

Der einzige technische Grund, den ich kenne, ist, dass einige funktionale Sprachen (und einige zwingende Sprachen, wenn ich mich erinnere) eine sogenannte Tail-Call-Optimierung haben, die es einer rekursiven Methode ermöglicht, die Größe des Stacks nicht bei jedem rekursiven Aufruf (dh dem rekursiven Aufruf) zu erhöhen ersetzt mehr oder weniger den aktuellen Aufruf auf dem Stapel).

Beachten Sie, dass diese Optimierung bei keinem rekursiven Aufruf funktioniert, sondern nur bei rekursiven Methoden mit Endaufruf (dh Methoden, die zum Zeitpunkt des rekursiven Aufrufs den Status nicht beibehalten).

Steven Evers
quelle
1
(1) Eine solche Optimierung gilt nur in sehr speziellen Fällen - das Beispiel von OP ist dies nicht, und viele andere einfache Funktionen erfordern besondere Sorgfalt, um rekursiv zu werden. (2) Eine echte Tail-Call- Optimierung optimiert nicht nur rekursive Funktionen, sondern beseitigt auch den Platzbedarf für jeden Aufruf, auf den unmittelbar eine Rückkehr folgt.
@delnan: (1) Ja, sehr wahr. In meinem 'ursprünglichen Entwurf' dieser Antwort hatte ich Folgendes erwähnt: (2) Ja, aber im Zusammenhang mit der Frage dachte ich, dass dies nicht zu erwähnen wäre.
Steven Evers,
Ja, (2) ist nur eine nützliche Ergänzung (auch wenn sie für einen weiterführenden Stil unverzichtbar ist), Antworten, die nicht erwähnt werden müssen.
1

Sie werden wollen , betrachten Garbage Collection schnell, aber ein Stapel ist schneller , ein Papier über die Verwendung , was C - Programmierer als „Haufen“ für das Stack - Frames in kompilierte C. Ich glaube , der Autor mit Gcc gebastelt denken würde , das zu tun, . Es ist keine definitive Antwort, aber das könnte Ihnen helfen, einige der Probleme mit der Rekursion zu verstehen.

Die Alef-Programmiersprache , die früher mit Plan 9 von Bell Labs geliefert wurde, hatte eine "Werden" -Anweisung (siehe Abschnitt 6.6.4 dieser Referenz ). Es ist eine Art explizite Optimierung der Endanruf-Rekursion. Das "aber es verbraucht Callstack!" Argumente gegen die Rekursion könnten möglicherweise beseitigt werden.

Bruce Ediger
quelle
0

TL; DR: Ja, sie tun
Rekursion ist ein Schlüsselwerkzeug in der funktionalen Programmierung, und daher wurde viel Arbeit in die Optimierung dieser Aufrufe gesteckt. Beispielsweise erfordert R5RS (in der Spezifikation!), Dass alle Implementierungen ungebundene Tail-Rekursionsaufrufe verarbeiten, ohne dass sich der Programmierer um einen Stapelüberlauf sorgt. Zum Vergleich führt der C-Compiler standardmäßig nicht einmal eine offensichtliche Tail-Call-Optimierung durch (versuchen Sie eine rekursive Umkehrung einer verknüpften Liste), und nach einigen Aufrufen wird das Programm beendet (der Compiler optimiert jedoch, wenn Sie Folgendes verwenden: O2).

Natürlich fibhat der Compiler in Programmen, die fürchterlich geschrieben sind, wie dem berühmten Beispiel, das exponentiell ist, kaum oder gar keine Möglichkeiten, seine "Magie" zu entfalten. Daher sollte darauf geachtet werden, die Compiler-Bemühungen bei der Optimierung nicht zu behindern.

EDIT: Mit dem fib Beispiel meine ich folgendes:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)
K.Steff
quelle
0

Funktionale Sprachen sind bei zwei sehr spezifischen Arten der Rekursion besser: der Schwanzrekursion und der unendlichen Rekursion. Sie sind genauso schlecht wie andere Sprachen bei anderen Rekursionen, wie Ihr factorialBeispiel.

Das heißt nicht, dass es in beiden Paradigmen keine Algorithmen gibt, die mit regulärer Rekursion gut funktionieren. Zum Beispiel ist alles, was sowieso eine stapelartige Datenstruktur erfordert, wie eine Tiefensuche, mit Rekursion am einfachsten zu implementieren.

Rekursion tritt bei der funktionalen Programmierung häufiger auf, wird aber auch viel zu oft verwendet, insbesondere von Anfängern oder in Tutorials für Anfänger, möglicherweise, weil die meisten Anfänger der funktionalen Programmierung die Rekursion zuvor bei der imperativen Programmierung verwendet haben. Es gibt andere funktionale Programmierkonstrukte wie Listenverständnisse, Funktionen höherer Ordnung und andere Operationen für Sammlungen, die konzeptionell für Stil, Prägnanz, Effizienz und Optimierungsfähigkeit viel besser geeignet sind.

Zum Beispiel ist Delnans Vorschlag von factorial n = product [1..n]nicht nur prägnanter und leichter zu lesen, sondern auch in hohem Maße parallelisierbar. Das Gleiche gilt für die Verwendung eines foldoder, reducewenn in Ihrer Sprache noch kein productCode integriert ist. Die Rekursion ist die Lösung für dieses Problem. Der Hauptgrund dafür, dass es in Tutorials rekursiv gelöst wird, ist, dass es ein Ausgangspunkt ist, bevor bessere Lösungen gefunden werden, und nicht als Beispiel für eine bewährte Methode.

Karl Bielefeldt
quelle