LogoSW

<< Home
<< andere "Rechnen"-Beiträge
↓↓  Ende

Rekursion

Inhalt

1. Einleitung
2. Sprache, Musik, Rundfunkreportage
3. Puppe in der Puppe
4. Zwischen zwei parallelen Spiegeln
5. Rad des Theodorus, Pythagoras-Baum, fraktale Muster
6. Mathematik: rekursive Definition
7. Rechner-Programmierung
8. Quellenverzeichnis

1. Einleitung

Rekursion ist ein in der Natur häufig beobachtbarer und in der Kultur oft nachgestellter Vorgang. Infolge der Anwendung in der Informatik in sogenannten rekursiven Programmen wurde der Begriff Rekursion eigentlich erst in jüngerer Zeit allgemein bekannt.

Rekursion ist ein grundsätzlicher natürlicher Vorgang bei der Reproduktion des Lebens, sowohl bei der Erhaltung der Arten als auch beim Wachstum und der Heilung nach Verletzungen von Individuen. Jede Generation von Lebewesen (Tiere und Pflanzen) erzeugt immerzu neue, ihren Individuen mehr oder weniger ähnliche Individuen der nächsten Generation. Bei der Heilung ist der reproduzierende Vorgang - im wesentlichen Zellteilung - immer derselbe. Die Erzeugung neuer Individuen ist hingegen nicht ein streng unveränderlicher Prozess. Es entstehen immer auch gegenüber den Vorgängern mutierte (variierte) Individuen. Diese Eigenschaft ist sowohl typisch bei der variierten Reproduktion des Lebens, als auch bei der verallgemeinerten Beschreibung dessen, was Rekursion ist: "Rekursion ist ... nicht einfache, sondern erweiterte Reproduktion; und Rekursion verschränkt Wiederholung und Variation mit dem Ziel, ein Neues hervorzubringen, ..." [1].

Mit diesem letzen Satz (Zitat) ist der Begrif Rekursion bereits teilweise definiert. Hinzugefügt werden muss - insbesondere bei kulturell nachgestellter Rekursion bzw. bei ihrer Anwendung durch den Menschen, dass die Vorschrift für die erweiterte Reproduktion immer gleich ist, also nur einmal genannt werden muss, und dass im Gegensatz zur Rekursion in der Natur diese nicht unendlich oft und lange vonstatten gehen kann. Automatisierte Rekursion wie in den rekursiven Computerprogrammen verlangt einen dezitierten Eingriff, damit sich der Automat nicht "totläuft".

Die eben angedeutete Definition ist noch nicht ausreichend. Die kultuelle Anwendung der Rekursion ist sehr vielseitig. Sie wird in den verschiedenen Anwendungsgebieten nie alle anderen Gebiete einschließend dargestellt bzw. definiert. Ich werde auch keinen, vermutlich nicht gelingenden Versuch, eine alle Gebiete einschließende allgemeine Definition zu finden, anstellen. Dafür werde ich eine größere Zahl von Anwendungsbeispielen besprechen.

2. Sprache, Musik, Rundfunkreportage

Das Vorkommen der Rekursion in der Sprache ist eigentlich noch kein typisches Anwendungsbeispiel, weil Sprechen zur Natur des Menschen gehört. Rekursion dabei ist, dass ein gesprochener Satz einen Nebensatz enthalten kann, der Nebensatz wieder einen Nebensatz enthalten kann, ... und so fort. Das zeigt einerseits den prinzipiell unnendlichen Vorgang Rekursion und andererseits, dass die Teilvorgänge und die Teilergebnisse einander ähnlich und aufeinander bezogen sind. Die Regeln für die Satz- und Nebensatzbildung sind gleich. In Realität wird die Unendlichkeit vermieden, weil dem Sprechenden bald einmal die Luft aus- und ihm und dem Hörer der Faden verloren-geht. In der Linguistik wird Rekursion als ein Begriff angesehen, "der die formale Eigenschaft von Grammatiken bezeichnet, mit einem endlichen Inventar von Elementen und einer endlichen Menge von Regeln eine unendliche Menge von Sätzen zu erzeugen" [2]. Das gilt vor allem für das Schreiben von Sätzen, womit jetzt ein typisches Anwendungsbeispiel gefunden ist. Aber auch hierbei bleibt es aus den o.g. Gründen bei nicht allzu langen Sätzen [3].

Dass Rekursion außer in der Sprache auch in der Musik vorkommt, ist naheliegend, denn: "Rekursive ... Strukturen sind in drei kognitiven Domänen grundlegend, in denen der Mensch besondere Fähigkeiten aufweist: der Sprache, der Musik und der Mathematik." [4] Bei der Musik wird oft von der Verschachtelung, die ein weiteres Merkmal von Rekursion ist, gesprochen. Wie die gesprochenen Nebensätze in Nebensätzen und Hauptsatz, sind z.B. auch in verschiedenen Tonarten gehaltene Themen einer Sonate ineinander verschachtelt. Hierbei verläuft der verschachtelte Vorgang Rekursion nicht wie im Allgemeinen überwiegend voran, sondern als Reprise zurück zum Anfang. Ein ähnlicher, rückführender verschachtelter Vorgang ist in den Nachrichtensendungen im Fernsehen und im Radio zu beobachten: Der Sprecher schaltet zu einen Reporter vor Ort des Geschehens um. Dieser lässt eine Person, die das Geschehen direkt beobachtet hat, ins Mikrofon sprechen. Der Vorgang kann auf verschiedenene Stufen hin- und hergehen, endet aber schließlich wieder im Studio beim Nachrichtensprecher [5]. Prizipiell ins Unendliche führendes Vorangehen findet in beiden Fällen nicht statt, dennoch wird von Rekursion, die ja auf Deutsch auch nur zurückkehren bedeutet, gesprochen.

Bevor ich mich der Mathematik, der dritten besonderen kognitiven Fähigkeit des Menschen und der darin vorkommenden Rekursion zuwende, behandle ich noch ein paar "Alltags"-Anwendungen von Rekursion.

3. Puppe in der Puppe


Abb.1  Die Puppe in der Puppe (Matrjoschka )                                                                                          [Wikipedia]
           Die vier kleineren Puppen finden jeweils Platz in der nächst größeren, die bis auf die kleinste hohl ist
           und aus zwei zusammensteckbaren Teilen besteht.
           Von den vier größeren Puppen sind die Oberteile abgenommen und daneben aufgestellt.

Die in Abb.1 gezeigte russische Matrjoschka besteht aus fünf ineinander steckbaren Puppen.

Eine Abbruchbedingung kann weggelassen werden, denn beliebig kleine Puppen lassen sich aus Holz gar nicht fertigen. Der Hersteller beendet seine Arbeit spätestens dann, wenn diese praktische Grenze erreicht ist.
Die Rekursion setzt nach dem Vorhandensein einer ersten Puppe ein; die Bildungsregel lautet:
Teile die Puppe etwa in der Mitte und höhle sie aus. Fertige eine ähnliche Puppe, die Platz innerhalb der vorherigen Puppe findet. (Teile die Puppe ...)

Bei diesem Anwendungsbeispiel ist gut erkennbar, dass Rekursion Variation einschließt: Die jeweils nächste Puppe ist keine reine Wiederholung, sie ist kleiner als die vorherige. Das individuelle bunte Bemalen der Puppen fällt nicht unter rekursives Vorgehen.

Das abstrakte Rekursions-Kennzeichen Verschachtelung wird hier konkret deutlich.

4. Zwischen zwei parallelen Spiegeln

Abb.2  Rekursive Bilderreihe wischen zwei Spiegeln in
           einem Personenaufzug  
           [Unendliche Spiegelfechtereien]

Die Bilderreihe zwischen zwei, Spiegeln ist nahe verwandt mit den natürlichen Rekursions-Vorgängen. Kultureller Beitrag ist lediglich, zwei Spiegel parallel zueinander anzuordnen. Die Rekursion braucht nicht angestoßen zu werden; sie ist zwischen den einander zugekehrten Spiegeln permanent "in Betrieb". Ein zwischen den Spiegeln angebrachter Gegenstand spiegelt sich in beiden Spiegeln. Da sich jeder der beiden Spiegel im anderen spiegelt, werden auch die in den Spiegeln vorhandenen virtuellen Bilder im jeweils anderen Spiegel mit gespiegelt. Das die Bilder erzeugende Licht läuft endlos zwischen den Spiegeln hin und her, was einen endlosen rekursiven Vorgang darstellt. Weil die Bildweite mit der Zahl der Spiegelungen zunimmt, wird der Bildwinkel zunehmend kleiner. Diese Änderung ist das Rekursions-Merkmal erweiterte Reproduktion. Die Bilder werden nicht nur immer kleiner und deshalb nicht mehr erkennbar, sondern sie werden auch schwächer, weil das Licht beim Lauf durch die Luft und bei jeder Reflexion an Stärke verliert. Aber auch ohne das gäbe es ein natürliches Ende, indem es keine Bilder, die kleiner als die Wellenlänge des Lichts sind, geben kann.

Den Eindruck, den man zwischen zwei parallelen Spiegeln sitzend erfährt, hat der Berner Mundartdichter und -sänger Mani Matter in einem Lied geschildert [6]. Er saß vor einem Spiegel beim Friseur, wo es einen zweiten Spiegel hinter dem Kunden gab. Matter erwähnt, dass er seinen Kopf auch von hinten - also beide Bildreihen - sah, was darauf hindeudet, dass die Spiegel nicht besonders genau parallel waren. In Abb.2 ist die Parallelität besser, denn die Foto-Kamera sieht sich nicht von hinten. Nur die Rückseite der seitlich befindlichen Person sieht sie teilweise noch; die Person selbst wird sich nur von vorne sehen.

5. Rad des Theodorus, Pythagoras-Baum, fraktale Muster

Meine ersten Rekursions-Beispiele aus der Mathematik sind rekursive Zusammenhänge, die sichtbar sind, also Graphiken.

Abb.3  Rad des Theodorus mit rekursiver Bildungsregel
           für die Radien                                 [Wikipedia]

Zuerst sei das Rad des im 5. Jahrhundert v.Chr. lebenden griechischen Mathematikers Theodorus, das überhaupt für das erste Beispiel für die - vermutlich noch unbewusste - Beschäftigung des Menschen mit Rekursion gehalten wird, besprochen (Abb.3). Es wird auch Wurzelschnecke genannt, weil Theodorus damit die Irrationalität der Wurzelwerte der Zahlen 3 bis 17 bewiesen haben soll (der Beweis für Wurzel aus 2 sei schon bekannt gewesen). Die rekursive Bildungsregel ist:
cn = (cn-12 + 1)   (mit c1 =√2) .
Typische Kennzeichen für Rekursion sind Bildungsregel und erweiterte Reproduktion von cn aus cn-1:
cn2 = cn-12 + 1 .

Diese Bildungsregel gilt bis zu unendlich großen Zahlen. Theodorus hat schon bei 17 abgebrochen, aber nur, weil sich die Schnecke ab 18 zu überdecken beginnt.


Abb.4  Pythagoras-Baum
           links:   Konstruktion bis zu 4 Außen-Verzweigungen                                                                     [Wikipedia]
           rechts: Konstruktion, abgebrochen als die Außen-Verzweigungen nicht mehr erklennbar sind           [Wikipedia]
           Anmerkung: Das vorgegebe Dreieck ist im linken Bild rechtwinklig, im rechten Bild ist es flacher

Beim sogenannten Pythagoras-Baum (Abb.4) wird von einem unter der Hypotenuse eines rechtwinkligen Dreiecks gezeichneten Quadrat ausgegangen. Daher der Name, obwohl die Rechtwinkligkeit im Dreieck keine Voraussetzung für das Gewinnen einer solchen Baumstruktur ist (siehe Abb.4, rechts).
Die rekursive Bildungsregel lautet:
1. Zeichne ein Quadrat und darüber ein Dreieck, dessen größte Seite mit der Quadtrat-Seite identisch ist.
2. Zeichne zwei weitere Quadrate mit Dreieck darüber, die der vorherigen Illustration ähnlich sind,
    und deren jeweilige Quadrat-Seite gleich lang wie eine der beiden freien Seiten des vorherigen Dreiecks ist.
3. Füge die beiden Illustrationen mit der Quadrat-Grundseite an die freien Seiten des Dreiecks an.
4. Zeichne nach gleicher Vorschrift aus den zwei im zweiten Schritt erzeugten Illustrationen vier weitere,
    ihnen ähnliche Illustrationen usw.

Das Besondere beim Pythagoras-Baum ist die sukzessive Verdopplung der entstehenden Illustrationen (in der Bildungsregel lässt sich das vermutlich deutlicher ausdrücken).

Rekursiv erzeugte Graphiken wie der Pythagoras-Baum können seit der Prägung des mathematischen Begriffs Fraktal (Benoît Mandelbrot, 1975) als fraktale Muster bezeichnet werden. Gleichzeitig mit dem Erscheinen des Begriffs Fraktal wendeten sich auch vermehrt Künstler rekursiv erstellbaren Graphiken zu, z.B. Karl Gerstner (Abb.5). Er und viele andere Künstler wurden dazu direkt durch die Darstellung der Mandelbrot-Menge ("Apfelmännchen") angeregt. So wie dort die Ränder der schwarzen Flächen durch immer kleinere Strukturn dargestellt sind, bestehen die Ränder des äußeren und der größeren inneren Kreise aus nach rekursivem Bildungsgesetz entstandenen, immer kleiner werdenden Kreisen. Das Füllen der Lücken zwischen diesen Kreisen und zwischen ihnen und den gedachten Rändern mit ebenfalls Kreisen verschiedener Größe ist möglicherweise ein gesonderter rekursiver Vorgang.


Abb.5  Karl Gerstner: Hommage à Mandelbrot , 1976/1988                                                                                   [7]

6. Mathematik: rekursive Definition

Diese in der Mathematik gebrauchte Wortkombination ist in zweifacher Hinsicht verwirrend:
1. Es handelt sich nicht darum, Rekursion zu definieren. Mehrere mögliche, anstatt einer einheitlichen Definition der Rekursion, wurden im bisherigen Text verstreut angegeben.
2. Es wird der Versuch unternommen, mathematische Funktionen mithilfe des Vorgangs Rekursion zu definieren. Dabei wird außer Betracht gelassen, "dass eine rekursive Definition nie etwas durch sich selbst, sondern immer durch einfachere Versionen ihrer selbst definiert." [8].

Ich persönlich fasse den Begriff Definition enger auf: ein Sachverhalt wird verbindlich in einer bestimmten Weise benannt. Für das, was hier und auch anderenorts oft gemeint ist, verwende ich lediglich beschreiben mithilfe von erkannten Zusammenhängen, gewissermassen unverbindlich beschreiben, oder einfach auch nur erklären.









Abb.6   Beispiele "rekursiver mathematischer
            Definitionen"                                [9]



In Abb.6 sind ein paar solcher " Definitionen" aufgeführt. Der jeweilige Algorithmus ist in Worten angegeben. Er besteht aus jeweils nur zwei Angaben. Sie werden hier aufgeführt, weil sie leicht zu verstehen sind. Dass sie aber einen rechnerischen Nutzen vernitteln, ist nicht ersichtlich. Selbstverständlich bereichern solche "rekursiven Definitionen" die Mathematik. Die Nutzenfrage stellt sich dort grundsätlich nicht.

7. Rechner-Programmierung

Die o.g. Beispiele aus der Mathematik sind zu leicht, um sie für sogenanntes rekursives Programmieren zu benutzen, sie sind dafür sogar ungeeignet: "Tatsächlich hat die Erklärung des Konzeptes rekursiver Algorithmen anhand von ungeeigneten Beispielen wesentlich zur Entstehung einer weitverbreiteten Abneigung und Antipathie gegen die Rekursion in der Programmierung beigetragen und zur Gleichsetzung von Rekursion mit Ineffizienz geführt." [9a] Rekursive Programme benötigen nämlich mehr Speichervolumen im Rechner als konventionelle, sogenannte iterativ formulierte Programme und sind auch bereits in solchen einfachen Ausführungen schwerer zu verstehen. "Rekursive Algorithmen eigenen sich besonders, wenn das zugrundeliegende Problem .... rekursiv definiert" [9a] ist. Die rekursive Definition in den genannten Beispielen existiert nicht à priori, sondern sie ist das Ergebnis mathematischer Übungen. Es "bedeutet nicht, dass eine ... rekursive Definition eine Garantie dafür bietet, dass ein rekursiver Algorithnus der beste Weg zur Lösung des Problems ist." [9a]

Nikolaus Wirth "zeigt die Entwicklung rekursiver Programme in Fällen, in denen Rekursion angebracht ist", zahlreich auf über 50 Seiten seines Buches [9b]. Die dabei gelösten Probleme sind alle recht anspruchsvoll, so dass hier ncht darauf eingegangen werden kann. Lediglich erwähnt sei das Problem der acht Damen [9c], das C.F. Gauss 1850 untersuchte. Es war analytisch nicht vollständig lösbar. Die Lösung gelang erst mithilfe der heutigen automatischen Rechner. Dafür, dass auf einen Schachbrett acht Damen so aufgestellt sind, dass sie sich nicht gegenseitig bedrohen, gibt es 12 signifikant verschiedene, nicht symmetrische Lösungen. Das in Pascal geschriebene Programm nimmt nicht einmal 1 Seite des Buches ein [9d]. Es verlockt dazu, es gelegentlich einmal austzprobieren. Zum Programm-Code ist anzumerken, dass es den sogenannten Selbstaufruf damals, als die 3. Auflage des Buches erschien, noch nicht gab. Umgeschrieben darauf sind die von Wirth angegebenen rekursiven Programme etwas kürzer.

In Abb.7, rechts ist ein unter Verwendung eines Selbstaufrufes einer Funktion verfasstes rekursives Programm gezeigt.









Abb.7   Rechner-Programme für fak(n)
           (s. Abb.6, 3.)          [Wikipedia]


Die beiden Programme sind in Python geschrieben. Zum Vergleich ist links die iterative Version beigefügt als Hinweis darauf, dass jedes rekursive Programm prinzipiell auch als iteratives Programm erstellt werden kann. Die rekursive Variante enthält etwas weniger Code als die iterative.

Berechnet wird der Wert der Fakultätsfunktion f(n). Vorgegeben wird der Wert n (number) der Funktion factorial. In der letzten Zeile ruft sich die Funktion factorial mit dem Argument (n-1) selbst auf. Es wird solange ein Produkt mit der dekrementierten Zahl gebildet, bis die Zahl bei der 1 angelangt ist. Zum Beispiel ist 4! = 4 * 3 * 2 * 1 = 24. Die Zahl 1 ist die für den prinzipiell unendlich weiter gehenden Vorgang Rekursion nötige Abbruchbedingung. Der Abbruch erfolgt in der Zeile 3, nachdem die Prüfung in Zeile 2 positiv ausgefallen ist.

Der Begriff Selbstaufruf ist zum Schlagwort für rekursives Programmieren geworden [10].

Eine gängige Bemerkung zu Rekursion ist, dass sie auch eine Problemlösungsstrategie sei [10]. M.E. kann damit nur ihre Anwendung in der Informatik/Programmierung gemeint sein. In Sprache und Musik und ebenso von Künstlern wird Rekursion intuitiv angewendet. Dort gibt es kaum jemand, der Rekursion absichtlich zur Lösung irgend eines Problems benutzt. Mathematiker möchten sich auf ihre Arbeit bezogen wohl grundsätzlich nicht als Strategen titulieren lassen.

Niklaus Wirth ist ein bedeutender Vordenker für Rechner-Programmmierung. Zudem hat er mehrere Programmiersprachen (z.B. Pascal) geschaffen, deshalb zum Abschluss noch zwei Zitate aus seinem Buch [9]:

"Ein Objekt heißt rekursiv, wenn es sich selbst als Teil enthält oder mithilfe von sich selbst definiert ist." [9e]

Darin ist der Versuch enthalten, den Begriff Rekursion möglichst allgemein zu definieren. Dabei muss aber an weiter oben Gesagtes (siehe 6. Mathematik: rekursive Definition) erinnert werden, dass Definition von etwas nicht durch durch sich selbst erfolgen kann. Im Zitat wäre folglich z.B. so zu schreiben: ... mithilfe einer Variante seiner selbst beschrieben (oder erklärt) ist.

"Das Wesentliche der Rekursion ist die Möglichkeit, eine unendliche Menge von Objekten durch eine endliche Aussage zu definieren." [9f]

Das Zitat stammt aus dem Umfeld Mathematik/Informatik, sein Inhalt kann aber auch allgemein verstanden werden. Es handelt sich um eine Parallele zu einer weiter oben (siehe 2. Sprache, Musik, Rundfunkreportage) stehenden Aussage eines anderen Autors [2].

8. Quellen-Verzeichnis

[1] Hartmut Winkler: Über Rekursion, Teil 1, letzter Absatz
[2] Hadumod Bussmann: Lexikon der Sprachwissenschaft, Alfred-Kröner-Verlag, Stuttgart, 1990, S. 640
[3] Christian Morgenstern hat uns eine hübsche Persiflage auf die Möglichkeit eines beliebig langen Satzes in der
     Vorrede zu seinen Galgenliedern hinterlassen.
[4] Angela D. Friedrich: Was ist der Mensch? Sprache, Musik und Mathematik, de Gruyter, 2008, Vorwort
[5] Douglas R. Hofstadter: Gödel - Escher - Bach, Klett-Cotta-dtb, 2004, Seite 138
[6] Mani Mater: Bim Coiffeur (Liedvortrag | Liedtext in Mundart und in deutscher Übersetzung)
[7] Museum für Gegenwartskunst Basel und Galerie Littmann Basel: Karl Gerstner - Ideenskizzen und Bilder,
     Katalog, 1992, Seite 44
[8] Douglas R. Hofstadter: Gödel - Escher - Bach, Seite 137
[9] Niklaus Wirth: Algorithmen und Datenstrukturen, Teubner, 1975,
     Seiten 149/50: Beispiele "rekursiver mathematischer Definitionen"
[9a] Niklaus Wirth: Seite 152
[9b] Niklaus Wirth: Seiten 155 bis 188
[9c] Niklaus Wirth: Seiten 168 bis 173
[9d] Niklaus Wirth: Seite 172
[9e] Niklaus Wirth: Seite 149
[9 f] Niklaus Wirth: Seite 150
[10] Wikipedia: Rekursion


LogoSW Siegfried Wetzel, CH 3400 Burgdorf, Mai 2021

↑↑  Anfang
<< andere "Rechnen"-Beiträge
<< Home