Sind funktionale Sprachen rekursiver?

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.

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.

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.

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).

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.

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).

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.

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)))
 )
)

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.