Rekursion und Iteration sind Berechnungsvorschriften, die durch schrittweises Wiederholen elementarer Operationen
- die Komplexität einer Aufgabe so weit reduziert, dass sie lösbar wird oder
- die Rechengenauigkeit bis zu einem vorgegebenen Maß steigert.
Rad des Theodorus
Das Rad des Theodorus (griechischer Gelehrter, 465 v.Chr.) ist eines der ersten Beispiele einer Rekursion. Dieses Rad kann durch einen rekursiven Algorithmus gebildet werden:
Die Bildungsregel lautet:
Das Rad wird durch aneinander gelegte rechtwinklige Dreiecke gebildet, wobei die eine Kathete stets den Wert 1 hat, während die andere Kathete durch die Hypotenuse des vorangegangen Dreiecks gebildet wird. Nur das erste Dreieck hat gleichlange Katheten der Länge 1.
In mathematischer Notation sieht die rekursive Bildungsregel so aus:
\( \begin{array}{l}{c_0} = \sqrt 2 \\ \\{c_n} = \sqrt {c_{n - 1}^2 + 1} \end{array} \) Gl. 92
Die Rekursion wird deutlich, wenn durch fortlaufendes Einsetzen von Gl. 92
\( {c_n} = \sqrt{ { {\left( {\sqrt {c_{n - 2}^2 + 1} } \right)}^2} + 1} = \sqrt{c_{n - 2}^2 + 1 + 1} = \sqrt {c_{n - 2}^2 + 2} \) Gl. 93
alle cn bis auf den Startwert c0 zurückgeführt wurden:
\( {c_n} = \sqrt {c_0^2 + n} \) Gl. 94