Rekursion und Optimierung

Was ist Rekursion?

Rekursion ist eigentlich kein Sprachfeature, sondern nur eine einfache Programmiertechnik. Wenn etwas rekursiv abläuft, dann bedeutet das, dass eine Funktion sich selbst ruft, bzw. eine Funktion „X“ andere Funktionen ruft, die dann wieder die Funktion „X“ rufen. Wenn X also die Funktion Y ruft, Y ruft Z und Z ruft wieder X, auch dann haben wir eine Rekursion.

Wenn sich eine Funktion selbst ruft, kann man das häufig auch mit einer Schleife abbilden und man sollte sich das auch durchaus überlegen. Ein rekursiver Funktionsaufruf ist dann sinnvoll, wenn man für jeden einzelnen Funktionsaufruf Variablen benötigt und man die darin gespeicherten Informationen nicht wieder verlieren möchte, bis der rekursive Funktionsaufruf zurückkehrt. Bei eindimensionalen Objekten (Arrays oder Listen) werden daher häufig Schleifen verwendet. Bei mehrdimensionalen, wie Bäumen oder einem Document Object Model (DOM) wird die Sache allerdings schwieriger.

In Vorbereitung auf das nachfolgende Kapitel, werden wir uns nun Rekursionen ansehen. Dabei werden wir Wert auf die Funktionsweise legen, aber auch, wie und wann man Rekursionen vermeiden kann.

Fibonacci-Folge mit Rekursion

Um Rekursion aufzuzeigen, verwende ich gerne die Fibonacci-Zahlenreihe, da sie rekursiv einfach zu berechnen ist. Die Fibonacci-Folge ist eine Funktion, die für den Wert 0 Null zurückgibt und für den Wert 1 Eins. Jeder nachfolgende Wert ist die Summe der beiden vorhergehenden Werte.

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

Die Fibonaccifolge entspricht immer der Seitenlänge eines Quadrates: 0, 1, 1, 2, 3, 5, 8, 13, 21, …

Wenn wir uns also den Wert von f(2) ansehen, dann entspricht das f(1)+f(0), also hat f(2) den Wert 1. Für Werte größer 1 ist es also kein Problem eine rekursive Funktion aufzustellen:

unsigned int fibonacci( unsigned int fib )
{
  return fibonacci( fib-1 ) + fibonacci( fib-2 );
}

Diese Funktion wird allerdings kein Ende finden, sie wird sich immer weiter selbst aufrufen. Egal welche Zahl übergeben wird, früher oder später wird ein Aufruf der Funktion mit dem Parameter 1 aufkommen und hier muss Schluss sein. Diese Bedingung nennt man Rekursionsanker. Diesen fügen wir nun nochmals ein. Damit die Funktion auch für den Wert 0 funktioniert, muss dieser Wert ebenfalls abgefragt werden:

unsigned int fibonacci( unsigned int fib )
{
  if     ( fib == 0 ) return 0;
  else if( fib == 1 ) return 1;
  else                return fibonacci( fib-1 ) + fibonacci( fib-2 );
}

Hier haben wir nun die Mathematik der Fibonacci-Folge 1:1 mit einer rekursiven Funktion abgebildet.

Optimierung

Wo für einen Mathematiker die Geschichte zu Ende ist, muss der Informatiker sich leider tiefer mit der Materie beschäftigen. Die Mathematik interessiert sich lediglich für die Frage, ob Aussagen richtig oder falsch sind. Die Informatik - und damit der Programmierer - muss sich zusätzlich darüber Gedanken machen, wie schnell diese Aussage, bzw. ein korrektes Ergebnis geliefert werden kann.

Jede Anweisung, die der Computer ausführt kostet Zeit. Nun haben wir heutzutage ja extrem schnelle Computer, so dass Optimierung eigentlich nicht mehr so dringend notwendig ist.

Schauen wir uns also zunächst die Werte der Fibonacci-Folge an.

Ich nehme gerne die Fibunacci-Folge, weil sie sich hervorragend eignet, um auch schnellste Computer in die Knie zu zwingen, denn was passiert: Um fibunacci(4) zu bestimmen, müssen wir fibonacci(3) und fibonacci(2) bestimmen und addieren. Für fibonacci(3) benötigen fibonacci(2) und fibonacci(1). Wie müssen hier also fibonacci(2) schon doppelt bestimmen, fibonacci(1) bereits dreimal. Das wird alles addiert: 3x fibonacci(1) ⇒ 3. 1 ist ist eigentlich der einzige Wert, der uns wirklich eine Information zurückliefert - nämlich 1. Diese ganzen 1'er werden dann addiert. Das ist ja weiter nicht schlimm, denn die Werte sind ja soweit überschaubar.

Schauen wir uns die Fibonacci-Folge doch einmal etwas weiter an.

fib(x) Wert fib(x) Wert fib(x) Wert fib(x) Wert
0 0 1 1 2 1 3 2
4 3 5 5 6 8 7 13
8 21 9 34 10 55 11 89
12 144 13 233 14 377 15 610
16 987 17 1597 18 2584 19 4181
20 6765 21 10946 22 17711 23 28657
24 46368 25 75025 26 121393 27 196418
28 317811 29 514229 30 832040 31 1346269
32 2178309 33 3524578 34 5702887 35 9227465
36 14930352 37 24157817 38 39088169 39 63245986
40 102334155 41 165580141 42 267914296 43 433494437
44 701408733 45 1134903170 46 1836311903 47 ?

Wir erkennen also, dass die Fibonacci-Folge ziemlich schnell durch die Decke schießt. Warum steht bei 47 ein Fragezeichen? Diese Zahl ist bereits so groß, dass sie mit einem Integer nicht mehr repräsentiert werden kann. Der Computer gibt für fibonacci(47) den Wert -1323752223 heraus und ein Intel i7 mit 2,8 GHz benötigt etwa 22 Sekunden, um das herauszufinden.

Wenn wir also Anweisungen sparen wollen, so können stellt sich die Frage, ob als Parameter 0 übergeben wurde, nur für den Fall, dass dieser Wert beim ersten Aufruf übergeben wird und für den Fall, dass man fibonacci(2) abfragt, was fibunacci(1)+fibunacci(0) entspricht.

Bei fibonacci(2) kommt das gleiche heraus, wie bei fibonacci(1). Wir können also eine Bedingung umformulieren:

unsigned int fibonacci( unsigned int fib )
{
  if( fib == 0 ) return 0;
  if( fib <= 2 ) return 1;  // <- geändert
 
  return fibunacci( fib-1 ) + fibunacci( fib-2 );
}

Statt zu fragen, ob (fib == 1) haben wir nun die Frage (fib ⇐ 2). Dieser Vergleich ist genauso zeitintensiv wie der, den wir austauschen. Aber damit haben wir kein Problem mehr für fibonacci(2) gelöst. Nun brauchen wir die Frage (fib == 0) nur noch für den Startfall - und den können wir auch getrennt betrachten.

unsigned int fibonacci_intern( unsigned int fib )
{
  if( fib <= 2 ) return 1;
 
  return fibonacci_intern( fib-1 ) + fibonacci_intern( fib-2 );
}
 
unsigned int fibonacci( unsigned int fib )
{
  if( fib == 0 ) return 0;
 
  return fibonacci_intern( fib );
}

Nun haben wir die Frage ( fib == 0 ) aus dem rekursiven Teil der Funktion entfernt. Die diese Funktion sich sehr häufig aufruft, sparen wir damit sehr schnell sehr viele überflüssige Abfragen, was die Berechnung deutlich beschleunigt.

fib(46) benötigt mit der nicht optimierten Funktion knapp 17 Sekunden, mit oben beschriebenen Beispiel ungefähr 11 Sekunden.

Wichtig ist mir hier, darauf zu achten, überflüssige Abfragen möglichst zu vermeiden. Das wird in dem Fall dadurch gestaltet, dass eine Frage, die nur einmal gestellt werden muss (nämlich ob fib == 0 ist) auch wirklich nur einmal gestellt wird und die Rekursion in einer anderen Funktion abläuft, die diese Frage nicht mehr stellt. Dies gilt nicht ausschließlich bei der Rekursion - alles, was häufig ausgeführt wird, sollte mit einem Auge auf die Optimierung von Abfragen geschrieben sein. Das gilt also ebenso besonders für Algorithmen, die innerhalb von Schleifen laufen. Hier sollten einmalige Abfragen oder Berechnungen auch nicht in der Schleife stattfinden, sondern davor durchgeführt werden und das Ergebnis zwischengespeichert werden.

Algorithmen an die Maschine anpassen

Wir haben nun die mathematische Formulierung auf die Maschine gebracht, es noch ein wenig optimiert und die Maschine wird so auch Lösungen liefern. Und trotzdem taugt diese Lösung für einen brauchbaren Entwickler nichts.

Im Gegensatz zum Mathematiker geht es beim Software-Entwickler nicht nur darum eine Lösung zu finden, sondern es geht zusätzlich darum, eine Lösung zu finden, die für die Maschine effektiv ist. Die Leistung eines Entwicklers ist also zusätzlich sich das Problem anzusehen und Lösungen zu suchen, die das gleiche Ergebnis liefert, aber schneller Ergebnisse liefert.

Was ist hier überhaupt das Problem? Im Prinzip passiert hier nichts weiter, als dass hier laufend 1 (nämlich den Rekursionsanker) addiert wird. Die Fibonacci-Folge steigt extrem stark an, das bedeutet, dass der Computer sehr viel damit beschäftigt ist, sehr viele Funktionen aufzurufen, um irgendwann mal 1 zu addieren.

Also schauen wir uns das Problem nochmal aus der Sicht eines Entwicklers an.

Addiert wird immer das Resultat der beiden vorherigen Fibonaccizahlen. Schauen wir uns mal an, wie sich die 20. Fibonaccizahl berechnet:

<m>fibonacci(20) = fibonacci(19) + fibonacci(18)</m>

Nun gehen wir weiter und fügen wir die Rekursion für fibonacci( 19 ) ein:

<m>fibonacci(20) = (fibonacci(18) + fibonacci(17)) + fibonacci(18)</m>

Und das können wir zusammenstreichen:

<m>fibonacci(20) = 2*fibonacci(18) + fibonacci(17)</m>

Genauso könnte man jetzt die 18. Fibonacci-Zahl in fibonacci(16) + fibonacci(17) aufteilen, entsprechend ist

<m>fibonacci(20) = 2*(fibonacci(16) + fibonacci(17)) + fibonacci( 17 )</m> <m>fibonacci(20) = 2*fibonacci(16) + 3*fibonacci(17)</m>

Der Punkt ist, dass die Werte für fibonacci(16) und fibonacci(17) nicht entsprechend multipliziert werden, sondern sie werden laufend neu berechnet, sie werden eben nicht gespeichert.

Bisher haben wir die Sache so aufgezogen, dass wir uns entsprechend der mathematischen Formulierung runtergehangelt haben und uns damit sehr viel Arbeit doppelt und dreifach gemacht haben.

Also schauen wir uns an, wie man das Ganze noch aufbauen kann. Wir drehen den Spieß mal um:

<m>fib( n-2 ) + fib( n-1 ) = fib( n )</m>

Wenn wir uns also fib(n-2) und fib(n-1) merken, dann können wir fib(n) sehr billig berechnen:

unsigned int fibonacci( unsigned int fib )
{
  if( fib == 0 ) return 0;
  if( fib == 1 ) return 1;
 
  unsigned int prepre = 0;
  unsigned int pre = 1;
  unsigned int current;
 
  for( int i = 1; i < fib; i++ )
  {
    current = pre + prepre;
 
    prepre = pre;
    pre = current;
  }
 
  return current;
}

Dieser Algorithmus funktioniert anders als die mathematische Formulierung und ist dennoch gleichwertig. Im Gegensatz zum vorherigen Ansatz berechnet er jedoch nichts doppelt, sondern entwickelt die gesuchte Lösung auf einem gradlinigen Weg.

Um die benötigte Zeit für diesen Algorithmus zu berechnen, müsste man aufwendiger testen, weil die Zeitspanne einfach zu kurz ist. Sie ist mit einfachen Mitteln nicht mehr messbar.

Ziel dieser Lektion

Wichtigstes Ziel dieser Lektion ist zu sehen, dass man manche Probleme vergleichsweise einfach lösen kann, indem man eine Funktion sich selbst rufen lässt. Diese Funktionen nennt man Rekursion.

Ein guter Programmierer ist bemüht möglichst wenige Fragen zu stellen und Algorithmen so zu formulieren, dass unnötige sich wiederholende Fragestellungen möglichst wegfallen. Rekursionen vereinfachen das Leben, wenn man rekursive Probleme hat. Diese finden sich häufig bei Baum-artige Datenstrukturen, die wir uns im im nächsten Kapitel ansehen werden. Sollte sich ein Problem ohne Rekursion besser lösen lassen, sollte man auf Rekursionen verzichten.

Programmierung bedeutet nicht nur abschreiben von mathematischen Lösungen, sondern auch anpassen von Lösungen auf die Besonderheiten und Einschränkungen, die die Maschine vorgibt. In dieser Lektion ging es darum, das Laufzeitverhalten zu optimieren. Ich möchte hier aber auch darauf hinweisen, dass Computer begrenzten Speicher besitzen: Eine Problematik, die sich für einen Mathematiker nicht stellt. Hieraus ergeben sich das Problem, dass ein Rechner nicht immer exakte Ergebnisse liefern kann.

siehe auch