Hallo habr
Heute setzen wir unsere Forschung zur funktionalen Programmierung im Kontext von EcmaScript fort, dessen Spezifikation auf JavaScript basiert. In den vorhergehenden Artikeln des Zyklus wurden folgende Themen behandelt:
- Reine Funktionen, Lambdas, Immunität
- Zusammensetzung, Currying, Teilanwendung
Rekursion
Wie immer hilft uns Wikipedia bei der Suche nach einer Definition:
Rekursion - die Definition, Beschreibung, Abbildung eines Objekts oder Prozesses innerhalb dieses Objekts oder Prozesses selbst, dh die Situation, in der das Objekt Teil von sich selbst ist. Der Begriff "Rekursion" wird in verschiedenen Spezialgebieten des Wissens verwendet - von der Linguistik bis zur Logik, findet jedoch in Mathematik und Informatik die größte Anwendung.
Rekursion bezieht sich für die Programmierung auf
Prozesse, die sich in ihrem Körper selbst aufrufen . Eine rekursive Funktion hat mehrere obligatorische Komponenten:
- Terminalbedingung - Beendigungsbedingung
- Die Regel, die sich tief in die Rekursion hineinbewegt
Betrachten Sie das beliebteste Beispiel für eine rekursionsfaktorielle Berechnung.
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Wir unterscheiden die charakteristischen Komponenten einer rekursiven Funktion. Endzustand
if (n === 0) { return 1; }
und Rekursionsregel
return n * factorial(n - 1);
Es ist wichtig zu wissen, dass Rekursion kein spezifisches Merkmal von JS ist, sondern eine in der Programmierung weit verbreitete Technik.
Rekursive und iterative Prozesse
Rekursion kann auf zwei Arten organisiert werden: durch einen rekursiven Prozess oder durch einen iterativen.
Wir haben den rekursiven Prozess bereits gesehen:
const factorial = (n) => { if (n === 0) { return 1; } return n * factorial(n - 1); }
Eine iterative Lösung des Fakultätsproblems würde folgendermaßen aussehen:
const factorial = (n) => { const iter = (counter, acc) => { if (counter === 1) { return acc; } return iter(counter - 1, counter * acc); }; return iter(n, 1); };
Beide Optionen sind Rekursionen. Beide Lösungen weisen Merkmale auf, die für eine Rekursion charakteristisch sind: die Endbedingung und die Bewegungsregel entlang der Rekursion. Schauen wir uns ihre Unterschiede an.
Der rekursive Prozess bei jedem Schritt erinnert sich an die Aktion. was getan werden muss. Wenn er die thermischen Bedingungen erreicht hat, führt er alle erinnerten Aktionen in umgekehrter Reihenfolge durch. Lassen Sie uns mit einem Beispiel veranschaulichen. Wenn der rekursive Prozess Fakultät 6 berücksichtigt, muss er sich 5 Zahlen merken, um sie am Ende zu zählen, wenn Sie nicht weiterkommen und nicht rekursiv tiefer in die Tiefe vordringen können. Wenn wir uns beim nächsten Funktionsaufruf irgendwo außerhalb dieses Aufrufs befinden, werden diese gespeicherten Nummern gespeichert.
Es sieht ungefähr so aus:
factorial(3);
Wie Sie sehen, besteht die Grundidee eines rekursiven Prozesses darin, die Berechnung auf das Ende zu verschieben.
Ein solcher Prozess erzeugt
einen zeitvariablen Zustand , der "irgendwo" außerhalb des aktuellen Funktionsaufrufs gespeichert ist.
Ich denke, Sie erinnern sich, dass wir im ersten Artikel der Reihe über
funktionale Programmierung über die Bedeutung von Immunität und Zustandsmangel gesprochen haben. Ein Zustand verursacht viele Probleme, die nicht immer einfach zu handhaben sind.
Ein iterativer Prozess unterscheidet sich von einem
rekursiven in einer festen Anzahl von Zuständen. Bei jedem Schritt berücksichtigt der iterative Prozess alles, was er berechnen kann, sodass jeder Schritt der Rekursion unabhängig vom vorherigen erfolgt.
Es sieht so aus:
iter(3, 1);
Ich denke, es ist offensichtlich, dass ein iterativer Prozess weniger Speicher verbraucht. Daher sollten Sie es immer verwenden, wenn Sie eine Rekursion erstellen. Einzige Ausnahme: Wenn wir den Wert erst berechnen können, wenn der thermische Zustand erreicht ist.
Baumrekursion
Viele Leute denken, dass Bäume und die Arbeit mit ihnen etwas sehr Abstruses, Komplexes und für bloße Sterbliche unverständliches sind. Dies ist eigentlich nicht der Fall. Jede hierarchische Struktur kann in Form eines Baumes dargestellt werden. Auch menschliches Denken ist wie ein Baum.
Um die Baumrekursion besser zu verstehen, schauen wir uns ein einfaches und beliebtes Beispiel an: Fibonacci-Zahlen.
Fibonacci-Zahlen - Elemente einer numerischen Folge 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, ... (Sequenz A000045 in OEIS), wobei die ersten beiden Zahlen entweder 1 und 1 oder 0 und 1 sind und jede nachfolgende Zahl gleich der Summe der beiden vorherigen Zahlen ist. Benannt nach dem mittelalterlichen Mathematiker Leonardo von Pisa (bekannt als Fibonacci).
Mathematisch ist es recht einfach, eine Beschreibung (und deklarative Programmierung ist die Beschreibung) dieser Sequenz zu formulieren:
fib(n) = [ 0 n = 0,//(1) 1 n = 1,//(2) fib(n-1) + fib(n-2) ]
Gehen wir nun von der Mathematik zum logischen Denken über (schließlich müssen wir Programmlogik schreiben). Um fib (5) zu berechnen, müssen wir fib (4) und fib (3) berechnen. Um fib (4) zu berechnen, müssen wir fib (3) und fib (2) berechnen. Um fib (3) zu berechnen, müssen wir fib (2) usw. berechnen, bis wir in unserem mathematischen Modell zu den bekannten Werten (1) und (2) gelangen.
Zu welchen Gedanken sollte unser Denken führen? Natürlich sollten wir die Rekursion verwenden. Die thermische Bedingung kann als n <= 1 formuliert werden. Anstelle eines Rekursionszweigs (wie in den vorherigen Beispielen) werden wir jedoch zwei Zweige haben: fib (n-1), fib (n-2).
const fib = (n) => (n <= 1 ? n : fib(n - 1) + fib(n - 2));
Diese Lösung hat ein deutliches Minus! Es wird das Ergebnis desselben Wertes von n mehrmals in verschiedenen Zweigen berücksichtigt. Um dieses Problem zu lösen, gibt es eine funktionale Programmiertechnik namens
Memoization , über die wir in einem der folgenden Artikel sprechen.
Fazit
Rekursion ist ein sehr leistungsfähiges Programmierwerkzeug. Lassen Sie mich daran erinnern, dass wir in der Regel einen iterativen Prozess verwenden. Die Verwendung eines rekursiven Prozesses lohnt sich nur, wenn das Zwischenergebnis nicht bei jedem Schritt der Rekursion berechnet werden kann.