Rekursion
Wenn etwas sich selbst in irgendeiner Form enthält, wenn also zum Beispiel eine Methode sich selbst aufruft oder eine Definition sich selbst verwendet, dann spricht man von Rekursion. Rekursive Vorgänge können relativ kurz und elegant programmiert werden, sind aber oft nicht leicht zu verstehen.
Die Fakultätsfunktion (eine einstellige Operation auf der Menge der natürlichen Zahlen) kann wie folgt beschrieben werden:
n! =def 1·2·3·...·(n−1)·n
für alle n ∈∈ ℕ.
Diese Definition ist unmittelbar verständlich aber in gewisser Hinsicht unbefriedigend. Zum einen stören die mathematisch unpräzisen
Pünktchen ... und zum anderen muss noch 0! =def 1
zusätzlich festgelegt werden. Eine Alternative ist es, die Fakultätsfunktion für alle
natürlichen Zahlen n rekursiv so zu definieren:
n! =def
|
|
1, falls n = 0; |
| n·(n−1)!, falls n > 0. |
Die Implementierung dieser Definition in Java sieht beispielsweise so aus:
public static int fac(int n) {
if (n == 0) return 1; // Rekursionsanfang
else return n*fac(n-1); // Rekursionsschritt
}
Ein anderes, klassisches Beispiel einer rekursiven Definition in der Mathematik betrifft die Fibonacci-Zahlen:
fib(n) =def
|
|
0, falls n = 0; |
1, falls n = 1; |
||
| fib(n−1) + fib(n−2), falls n > 1. |
Werden zwei beliebige natürliche Zahlen mit a bzw. b bezeichnet, so lässt sich diese Definition verallgemeinern zur Definition der Lucas-Zahlen:
luc(n) =def
|
|
a, falls n = 0; |
b, falls n = 1; |
||
| luc(n−1) + luc(n−2), falls n > 1. |
Mit Hilfe der Fibonaccifolge
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
kann man in natürlicher Weise folgende Spirale konstruieren, die nach einem der größten europäischen Mathematiker des Mittelalters Leonardo Pisano (1170−1250) benannt ist (Leonardo nannte sich selbst „Fibonacci“). Hierzu werden Viertelkreise aneinander gesetzt, deren Radien den Fibonacci-Zahlen entsprechen:
Eine solche Spirale lässt sich (näherungsweise) unter Verwendung einer Turtle-Grafik rekursiv programmieren (→ Javaprojekt FibonacciSpiral):
void drawFibonacciSpiral(int n) {
turtle = new Turtle(this, 360, 680, -30);
drawArc(n, 0);
}
void drawArc(int n, int m) {
if (n == -1) return;
turtle.goInACircleToTheLeft(10*fib(m), 90);
drawArc(n-1, m+1);
}
fac,
fib und
drawArc sind Beispiele für primitive Rekursionen, denn
jede dieser Methoden kann durch ein iteratives Verfahren (etwa unter
Verwendung einer Schleife) ersetzt werden.
Findet man innerhalb einer Figur verkleinerte Kopien von ihr selbst, so wird eine solche Figur selbstähnlich genannt. Besteht eine Figur vollständig aus verkleinerten Selbstkopien, spricht man von strikter oder strenger Selbstähnlichkeit. Ein Sierpinskidreieck beispielsweise ist strikt selbstähnlich. Es entsteht durch einen unendlichen Prozess: Aus einem „gefüllten“ Dreieck wird das Mitteldreieck entfernt, danach werden aus den entstandenen Teildreiecken die Mitteldreiecke entfernt, danach werden aus den dann entstandenen Teildreiecken ....
....
Auch dieser Konstruktionsprozess lässt sich mit Hilfe einer primitiven Rekursion realisieren (→ Javaprojekt SierpinskiTriangle).
Schwieriger wird es etwa bei der Darstellung der Folge derjenigen Polygonzüge, die der Hilbertkurve zustrebt. Die von David Hilbert 1891 entdeckte stetige Kurve füllt ein beliebig großes Quadrat vollständig aus. Die ersten Folgenglieder dieser Polygonzugfolge sehen so aus:
....
Die Konstruktion dieser Polygonzüge gelingt mit wechselseitiger Rekursion, indem zwei miteinander verschränkte Methoden sich gegenseitig solange aufrufen, bis die Abbruchbedingung erfüllt ist (→ Javaprojekt HilbertCurve).
