Einführung
Endrekursion
Eine Funktion ist endrekursiv, wenn das Letzte, was die Funktion ausführt, ein Aufruf ihrer selbst ist.
Jedes Mal, wenn eine Funktion aufgerufen wird, wird ein Stackframe mit ihren lokalen Variablen und Argumenten oben auf den Aufrufstapel gelegt.
Wenn eine Funktion zurückkehrt, wird der Stackframe vom Stapel entfernt.
Endrekursive Funktionen ermöglichen die Tail-Call-Optimierung (oder Tail-Call-Eliminierung).
Das ist eine Optimierung, die es dem nächsten Funktionsaufruf erlaubt, den letzten Stackframe wiederzuverwenden, wenn sicher ist, dass die vorherige Funktion ihn nicht mehr braucht.
Das entschärft die Sorge vor einem Überlauf des Aufrufstapels. Ein solcher Überlauf entsteht, wenn so viele Frames auf dem Aufrufstapel liegen, dass kein Speicher mehr übrig ist, um einen weiteren anzulegen.
Tail-Call-Optimierung in Elm
Unter bestimmten Bedingungen kann der Elm-Compiler beim Kompilieren nach JavaScript automatisch eine Tail-Call-Optimierung durchführen.
Die Optimierung kann bei einer rekursiven Funktion auftreten, wenn die letzte Operation in einem Zweig darin besteht, die Funktion selbst in einer einfachen Funktionsanwendung aufzurufen.
Schauen wir uns ein paar Beispiele an:
factorial : Int -> Int
factorial n =
if n <= 1 then
n
else
n * factorial (n-1)
Die obige Implementierung ist nicht endrekursiv, weil die letzte Operation im else-Zweig eine Multiplikation n * ist.
factorial : Int -> Int
factorial n =
factorialHelper n n
factorialHelper : Int -> Int -> Int
factorialHelper n resultSoFar =
if n <= 1 then
resultSoFar
else
factorialHelper (n-1) (n * resultSoFar)
Die obige Implementierung ist endrekursiv und wird optimiert, weil die letzte Operation im else-Zweig darin besteht, dass factorialHelper sich selbst aufruft.
Bei einer Funktion mit der Typsignatur Int -> Int wäre das nicht möglich, und in der Praxis erreicht man die Tail-Call-Optimierung oft dadurch, dass man Hilfsfunktionen definiert.
Anleitung
Piper ist eine begeisterte Pie-Bäckerin.
Niemand weiß, ob sie sich das Pie-Backen wegen ihres Namens ausgesucht hat oder ob sie ihren Namen an ihr Hobby angepasst hat.
Auf den ersten Blick klingt Letzteres nicht sehr wahrscheinlich, aber Piper ist, wie du siehst, absolut fasziniert von Pies.
Sie tüftelt ständig in der Küche, feilt an ihren Rezepten und verbessert ihr Handwerk, zur großen Freude ihrer Freunde.
Ihr neuestes Interesse?
Pies zu backen, die so rund wie möglich sind, bis hin zur mathematischen Perfektion, mit Hilfe ihrer Lieblingszahl, du ahnst es schon: π.
Piper hat eine wunderbare Formel entdeckt, mit der sich π iterativ berechnen lässt, die Newton/Euler-Konvergenztransformation:
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Hilf Piper, ihren mathematisch perfekten Pie zu backen, indem du π berechnest.
1. Fakultät
Wärmen wir uns zuerst auf.
Der Fakultätsoperator, üblicherweise als ! geschrieben, ist definiert als
0! = 1
n! = 1 * 2 * 3 * ... * n
Definiere die Funktion factorial, die die Fakultät endrekursiv berechnet.
factorial 4
-- 24
2. Doppelfakultät
Der Doppelfakultätsoperator, üblicherweise als !! geschrieben, ist definiert als
0!! = 1
n!! = 1 * 3 * 5 * ... * n (for odd n)
n!! = 2 * 4 * 6 * ... * n (for even n)
Definiere die Funktion doubleFactorial, die die Fakultät endrekursiv berechnet.
factorial 5
-- 15
factorial 6
-- 48
Definiere die Funktion pipersPi, die π mithilfe einer festen Anzahl von Termen aus der Formel der Newton/Euler-Konvergenztransformation endrekursiv annähert.
π / 2 = sum for k from 0 to infinity of ( k! ) / ( 2 * k + 1 )!!
Berechnen wir den ersten Term gemeinsam.
Für eine Obergrenze von 0 (statt unendlich) erhalten wir:
π / 2 ≈ Sum for k from 0 to 0 of ( k! ) / ( 2 * k + 1 )!!
π / 2 ≈ ( 0! ) / ( 2 * 0 + 1 )!!
π / 2 ≈ 0! / 0!!
π / 2 ≈ 1 / 1
π / 2 ≈ 1
π ≈ 2
Jeder zusätzliche Term verbessert die Näherung.
pipersPi 0
-- 2.0
pipersPi 1
-- 2.6666666
Lernübung
