Systematische Programmentwicklung
Rekursion
Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft.
Technisch bedeutet dies: Die Funktionsdefinition enthält einen Aufruf der Funktion selber. Wie kann das funktionieren? Die Funktion ist noch gar nicht fertig definiert, und schon ruft sie sich auf?
Doch, es funktioniert – jedenfalls dann, wenn es eine Bedingung gibt, bei der die Rekursion endet, und wenn derjenige Teil der Funktion, der dann ausgeführt wird, bereits fertig definiert ist. Sonst würde es tatsächlich nicht funktionieren.
Ein Beispiel für eine rekursive Funktion ist die rekursive Implementierung der Fakultätsfunktion n! = 1·2·3· ... ·n. Diese basiert auf der folgenden rekursiven Definition der Fakultätsfunktion:
| n! = |  |
|
Die entsprechende Implementierung einer rekursiven Funktion fac in der Programmiersprache Python lautet:
if n==0:
return 1
else:
return n * fac(n-1)
Wenn Sie zum Beispiel fac(3) aufrufen, ruft die Funktion ihrerseits fac(2) auf, dann noch einmal fac(1) und dann fac(0). Hier endet die Rekursion, und für diesen Fall ist bereits fertig definiert, was jetzt zu tun ist, nämlich return 1.
Probleme bei Rekursion
Bei der Umsetzung von Rekursionsgleichungen in ein rekursives Programm ist die Korrektheit der Implementierung nahezu automatisch gegeben. Ein paar Gedanken müssen Sie sich jedoch im Allgemeinen über zwei Punkte machen:
- Rekursionsbreite
- Rekursionstiefe
Was sich hinter diesen Punkten verbirgt, sehen Sie im Folgenden anhand von zwei Beispielen.
Rekursionsbreite
Betrachten Sie folgende rekursive Berechnung der Fibonacci-Zahlen 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
Die Funktion fib(n) liefert die n-te Fibonacci-Zahl (n = 0, 1, ...).
| fib(n) = | |
|
Die untenstehende Implementierung einer rekursiven Funktion fib entsprechend dieser Definition ist offenbar korrekt.
Leider aber ist sie hoffnungslos ineffizient. Denn es werden exponentiell viele Aufrufe der Funktion verursacht, nämlich fib(n) Aufrufe, um fib(n) zu berechnen.
if n==0 or n==1:
return 1
else:
return fib(n-2) + fib(n-1)
Aufgabe 1: Zeichnen Sie ein baumartiges Schema, um zu veranschaulichen, welche Aufrufe der Funktion fib verursacht werden, wenn Sie im Hauptprogramm fib(5) aufrufen.
Wie viele Aufrufe der Funktion fib kommen hierbei zusammen?
Überlegen Sie, wie der Aufrufbaum von fib(6) aussieht und wie viele Aufrufe der Funktion fib er enthält.
Schon bei n = 100 können Sie erstmal in Ruhe einen Kaffee trinken gehen, bis das obenstehende Programm den Wert fib(n) ausgerechnet hat. Tatsächlich lässt sich darüber streiten, ob das Programm überhaupt korrekt ist, denn beispielsweise für n = 1000 versagt es.
Das Problem besteht darin, dass eine exponentielle Rekursionsbreite zustande kommt, wie Sie anhand des Aufrufbaums erkennen.
Rekursionstiefe
Das Sortierverfahren Quicksort ist das schnellste Sortierverfahren, es benötigt nur n·log(n) Schritte, um n Daten zu sortieren. Dies gilt allerdings nur im Durchschnitt. Im schlechtesten Fall benötigt es n2 Schritte, und schlimmer noch, es verursacht dann eine Rekursionstiefe von n. Dann besteht schon bei etwa n = 2.000 die Gefahr, dass der Algorithmus mit der Fehlermeldung maximum recursion depth exceeded abstürzt. Typischerweise wollen Sie aber meist sehr viel mehr als 2.000 Daten sortieren.
Der Fehler wird durch einen sogenannten stack overflow verursacht, einen Überlauf des Aufrufstacks, in dem die unerledigten rekursiven Aufrufe gespeichert werden.
Abhilfe bei zu großer Rekursionstiefe
Grundsätzlich haben Sie zwei Möglichkeiten, um einen stack overflow zu vermeiden:
- Sie weisen das Betriebssystem an, einen größeren Stack zu verwenden; dadurch ermöglichen Sie eine größere Rekursionstiefe. In der Programmiersprache Python beispielsweise schreiben Sie
sys.setrecursionlimit(5000)
und legen hierdurch die maximale Rekursionstiefe auf den Wert 5000 fest. Vorher importieren Sie mit import sys noch das Modul sys.
- Sie schreiben eine endrekursive Funktion. Bei einer endrekursiven Funktion ist der rekursive Aufruf die letzte Aktion in der Funktionsdefinition. Bei einem rekursiven Aufruf wird alles, was im obersten Eintrag des Aufrufstacks gespeichert ist, fortan nicht mehr benötigt. Der oberste Stackeintrag kann daher einfach überschrieben werden.
Leider erkennt Python keine Endrekursion und überschreibt daher den obersten Stackeintrag nicht, sondern erzeugt einen neuen Eintrag. Die Erkennung von Endrekursion und eine entsprechende Stack-Strategie ist Aufgabe eines optimierenden Compilers.
Endrekursive Funktionen
Eine endrekursive Funktion beschreibt im Grunde genommen eine Iteration. Tatsächlich können Sie aus einem Iterationsschema in systematischer Weise eine endrekursive Funktion ableiten.
In bestimmten Fällen ist es auch möglich, mithilfe eines formalen Verfahrens eine rekursive Funktion in eine endrekursive Funktion umzuformen.
Divide and Conquer
Die Divide-and-Conquer-Strategie (Teile-und-Herrsche-Strategie) ist eine Entwurfsmethode für effiziente Algorithmen. Hierbei wird ein Problem gelöst, indem es in zwei Hälften aufgeteilt wird (divide), diese nach derselben Methode gelöst werden (conquer) und die Lösungen anschließend zusammengefügt werden (combine). Im Zuge der Aufteilungen wird das Problem irgendwann so klein, dass es auf andere Weise direkt gelöst werden kann.
Hier bietet sich die Rekursion an, um die Divide-and-Conquer-Strategie zu implementieren.
Beispiele sind die Sortieralgorithmen Quicksort und Mergesort, das Suchverfahren Binäre Suche oder der FFT-Algorithmus.
H.W. Lang mail@hwlang.de Impressum Datenschutz
Diese Webseiten sind größtenteils während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden