Rekursion |
Bisher können wir nur Programme schreiben, die mit Daten einer fixen Länge arbeiten.
In funktionalen Sprachen gibt es keine "for"-Schleifen. Daher müssen wir uns anders behelfen.
Beispiel: Gegeben eine Liste mit Zahlen, wollen wir jede davon quadrieren.
- Quadriere das erste Element der Liste
- Schreibe das Ergebnis an den Anfang vom quadrierten Rest der Liste
Rekursiver Ansatz:
(defn square-list [[first & rest]]
(if (nil? first)
'()
(conj (square-list rest) (* first first))))
(square-list '(3 5 6 12))
; => (9 25 36 144)
Eine Operation für jedes einzelne Element einer Sequenz anwenden zu wollen ist eine gängige Operation. Mit einer Higher Order Function können wir das abstrahieren
(defn apply-each [f [first & rest]]
(if (nil? first)
'()
(conj (apply-each f rest) (f first))))
(defn square [x]
(* x x))
(apply-each square '(3 5 6 12))
; => (9 25 36 144)
Das Pattern ist so gängig, dass es auch schon eine Funktion dafür gibt
(map #(* % %) '(3 5 6 12))
; => (9 25 36 144)
"map" ist allgemeiner und kann auf mehreren Sequenzen gleichzeitig laufen
(map * [1 2 3] [4 5 6])
; => (4 10 18)
Gängiges Pattern, um Werte umzuwandeln:
(def weekdays
{0 "Montag"
1 "Dienstag"
2 "Mittwoch"
3 "Donnerstag"})
(map weekdays [1 1 0 3])
; => ("Dienstag" "Dienstag" "Montag" "Donnerstag")
Mit Rekursion können wir theoretisch alles berechnen, was ein Computer (Turing Maschine) berechnen kann.
Anderes Beispiel: Fakultät
$\text{factorial}(n) = 1 \cdot 2 \cdot 3 \cdot \ldots \cdot n$
(defn factorial [n]
(if (= n 1)
1
(* n (factorial (- n 1)))))
(factorial 6)
; => 720
- (factorial 6)
- (* 6 (factorial 5))
- (* 6 (* 5 (factorial 4)))
- (* 6 (* 5 (* 4 (factorial 3))))
- (* 6 (* 5 (* 4 (* 3 (factorial 2)))))
- (* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
- (* 6 (* 5 (* 4 (* 3 (* 2 1)))))
- (* 6 (* 5 (* 4 (* 3 2))))
- (* 6 (* 5 (* 4 6)))
- (* 6 (* 5 24))
- (* 6 120)
- 720
Wir müssen uns die ganze Kette an Zwischenergebnissen merken und können das Ergebnis erst am Ende zusammenrechnen.
Brauchen Speicherplatz linear in der Anzahl an rekursiven Aufrufen.
Können wir das effizienter lösen?
(defn factorial-iter [product counter n]
(if (> counter n)
product
(factorial-iter (* product counter)
(+ counter 1)
n)))
(factorial-iter 1 1 6)
; => 720
(defn factorial-iter [product counter n]
(if (> counter n)
product
(factorial-iter (* product counter)
(+ counter 1)
n)))
- (factorial-iter 1 1 6)
- (factorial-iter 1 2 6)
- (factorial-iter 2 3 6)
- (factorial-iter 6 4 6)
- (factorial-iter 24 5 6)
- (factorial-iter 120 6 6)
- (factorial-iter 720 7 6)
- 720
Jetzt brauchen wir uns nicht die ganze Kette sondern immer nur den aktuellen Aufruf merken.
Wir brauchen nur noch konstanten Speicherplatz.
Für die Fakultät ist uns die genaue Reihenfolge der Multiplikationen egal. Wenn wir rückwärts zählen, kommen wir mit einem Parameter weniger aus:
(defn factorial-iter [product n]
(if (<= n 1)
product
(factorial-iter (* product n)
(- n 1))))
(defn factorial-iter [product counter n]
(if (> counter n)
product
(factorial-iter (* product counter)
(+ counter 1)
n)))
Wenn der rekursive Aufruf am Ende der Funktion kommt, nennen wir das Tail Recursion
Manche funktionalen Sprachen haben Compiler, die automatisch Tail Recursion optimieren.
In Clojure brauchen wir den speziellen Befehl "recur"
(defn factorial-iter [product counter n]
(if (> counter n)
product
(recur (* product counter)
(+ counter 1)
n)))
- Compiler Optimierung passiert sicher wenn wir es erwarten
- Keine Optimierung ohne explizite Anweisung
Vorteil von "recur"
Nachteil
Um ein schöneres Interface zu bekommen, können wir die Iteration als innere Funktion verbergen:
(defn factorial [n]
(defn factorial-iter [product counter]
(if (> counter n)
product
(recur (* product counter)
(+ counter 1))))
(factorial-iter 1 1))
Dafür gibt es ein eigenes Macro:
(defn factorial [n]
(defn factorial-iter [product counter]
(if (> counter n)
product
(recur (* product counter)
(+ counter 1))))
(factorial-iter 1 1))
(defn factorial [n]
(loop [product 1
counter 1]
(if (> counter n)
product
(recur (* product counter)
(+ counter 1)))))
Manchmal müssen wir eine Funktion mehrfach rekursiv aufrufen.
Beispiel: Fibonacci Sequenz (1 1 2 3 5 8 12 21 ...)
(defn fib [n]
(if (< n 2)
n
(+ (fib (- n 1)) (fib (- n 2)))))
Mit dieser Implementierung wächst die Anzahl rekursiver Aufrufe exponentiell mit dem Parameter n.
Hier ist eine bessere Implementierung möglich (siehe Übung)
Je nach Problem ist aber eine effizientere Lösung nicht immer möglich.
Viele Probleme können gut mit einem iterativen Ansatz gelöst werden.
Beispiel: Quadratwurzel mit Newtons Methode berechnen.
- Nimm eine beliebige Lösung $y$ (z.B. 1)
- Eine bessere Lösung ist der Durchschnitt zwischen $y$ und $\frac{x}{y}$.
Wir suchen $y = \sqrt{x}$, also die Zahl $y \geq 0$, für die $y^2 = x$ gilt.
Damit können wir einen Schritt definieren, um eine Lösung zu verbessern:
(defn average [x y]
(/ (+ x y) 2))
(defn improve [guess x]
(average guess (/ x guess)))
Den Verbesserungsschritt müssen wir nun "oft genug" wiederholen. Wie oft?
Z.B. bis wir nicht mehr als ein Epsilon weit weg sind: $|y^2 - x| < 0.0001$
(defn squared [x]
(* x x))
(defn good-enough? [guess x]
(< (abs (- (squared guess) x)) 0.0001))
Jetzt können wir unsere Wurzelfunktion (mit Tail Recursion) implementieren:
(defn sqrt [x]
(loop [guess 1]
(if (good-enough? guess x)
guess
(recur (improve guess x)))))
Baum Datenstrukturen und Graphen bieten sich oft sehr direkt für rekursive Algorithmen an.
Für viele KI und Optimierungsprobleme suchen wir eine Lösung in einem Baum oder einem Graphen.
Sehr oft wollen wir Operationen auf Sequenzen von Dingen ausführen.
Z.B. können wir mit "map" jedes Element 1:1 transformieren.
Behalte nur bestimmte Elemente einer Liste
(filter #(> % 8) [3 28 7 12 8 -2 15 9])
; => (28 12 15 9)
Wir wollen eine Liste mit Daten zu einem Element zusammenfassen
(def configurations
[{:flag1 true :path2 "abcd/efg"}
{:magic-number 1337 :path1 "efg/abcd"}
{:flag2 false :magic-number 42}])
(println (reduce conj configurations))
Zähle, wie oft jedes Element einer Liste vorkommt
(frequencies ["Apfel" "Birne" "Zitrone" "Apfel" "Apfel" "Zitrone"])
; => {"Apfel" 3, "Birne" 1, "Zitrone" 2}
Für viele Operationen gibt es schon einen passenden Helper
Clojure Dokumentation und Stack Overflow können helfen.
Vorteil von funktionalen Interfaces:
Stärkere Abstraktion von "wie" zu "was":
- Ich will Input Element einer Liste mappen
- Wie das bewerkstelligt wird kann die Maschine optimieren.
Map-Reduce Frameworks nehmen diesen Ansatz:
- Spezifizieren was für jeden Datensatz zu tun ist.
- Framework verteilt Aufgabe auf Cluster Knoten.
Wie sieht es mit der Performance aus?
- Persistant Data Structures kommen mit Overhead.
- Nicht optimierte Rekursion ist langsamer als eine Schleife.
- Keine selbstgebauten low-level Optimierungen möglich (AVX, SIMD, ...).
In der Regel ist die Performance der Sprache nicht das Bottleneck.
- Embedded Code (wenig Speicher, keine GC Zyklen)
- High Performance Computing
- Low-level Algorithmen
Ausnahmen: