Rekursion

Beschreibung

Eine Rekursion nennt man folgende Programmiertechnik: Eine Funktion ruft sich selbst auf! Die Idee dabei ist: Man führt ein Problem, das aus lauter Teilproblemen besteht, auf ein Problem von gleicher Art - aber geringeren Umfangs - zurück. Hä?

Also ein einfaches Beispiel:
Wir möchten die Fakultät einer Zahl n berechnen. Diese ist definiert als n!=n*(n-1)* ... * 2*1.
Gut man könnte das jetzt einfach mit einer for-Schleife regeln. Aber wir möchten ja testen was es mit dieser Rekursion auf sich hat:
Unser Problem ist, dass wir n-1 Multiplikationen durchführen müssen. Man könnte dieses Problem so zerlegen: n!=n*(n-1)!. Das bedeutet wir berechnen jetzt n! aus n und (n-1)!. Damit haben wir unser Problem vereinfacht und wir müssen nicht mehr n! ausrechnen, sondern nur noch (n-1)!. Und das soll einfacher sein - na klar. Man kann das ja weitermachen, bis man bei 1 ist. Und davon wissen wir, dass die Fakultät 1 ist.

Beispiele

Also Fakultät haben wir schon. n! wird zerlegt in n*(n-1)!, solange bis man bei 1 angelangt ist:

print "Berechne die Fakultaet einer Zahl >> ";
chomp($zahl=<STDIN>);

print $zahl."! = ".fakultaet($zahl).".\n";

###SUBS####

### fakultaet(Zahl)
# bestimme die Fakultaet einer Zahl
sub fakultaet{
  my $n=$_[0];

  if ($n<=1) {
    1; # gebe 1 zurueck
  }
  else {
    $n*fakultaet($n-1); # (*)
    # das ist die Rekursion; es wird
    # $n * die Fakultaet von n-1
    # berechnet und zurueckgegeben
  }
}

In der Zeile (*) wird zuerst die Funktion fakultaet($n-1) aufgerufen und ausgerechnet.
Wichtig bei einer Rekursion ist die Abbruchbedingung! Hier if ($n<=1); sonst könnte es leicht passieren, dass man ins unendliche läuft ...

Durchlauf durch eine Verzeichnisstruktur ist ein typisches Problem, das man mit Hilfe von einer Rekursion lösen kann. Was ist unser Problem: Wir möchten alle Files, Unterverzeichnisse und deren Files und Unterverzeichnisse und deren ... ausgeben.
Die Lösung - nur formal - die richtige gibt's in den Übungen:

Bestimme alle Files und Unterverzeichnisse im Verzeichnis.
Gebe die Files aus.
Mache das Gleiche mit allen Unterverzeichnissen.

Fibonacci-Zahlen lassen sich ebenfalls rekursiv berechnen. Also Fibonacci-Zahlen sind: 1 1 2 3 5 8 13 21 .... Entstehung dieser Zahlen: Gestartet wird mit 1 und 1. Die nächste Fibonacci-Zahl ist 3 - das ist die Summe der beiden vorangegangenen Zahlen. Und so geht es auch weiter. 2+3=5, 3+5=8. Will man nun eine beliebige Fibonacci-Zahl bestimmen kann man dies folgendermaßen tun:

print "Berechne die n-te Fibonacci-Zahl. Geben Sie n ein: >> ";
chomp($n=<STDIN>);

print "Die $n-Fibonacci-Zahl ist ".fibonacci($n).".\n";

###SUBS####

### fibonacci(n)
# bestimme die n-te Fibonacci-Zahl
sub fibonacci{
  my $n=$_[0];

  if ($n<=2) {
    1; # die ersten beiden Fib-Zahlen sind beide 1
  }
  else {
    fibonacci($n-1)+fibonacci($n-2);
  }
}

Hier wird zweimal die Funktion fibonacci innerhalb aufgerufen: einmal mit $n-1 und mit $n-2; das hat zur Folge, dass man beide Fälle bei der Abbruchbedingung berücksichtigen muss. Wenn man z. B. bei $n==3 angelangt ist, so ruft man fibonacci(2)+fibonacci(1) auf. In fibonacci(2) würde dann fibonacci(1)+fibonacci(0) aufgerufen werden. Das ist aber nicht möglich, da es keine 0-te Fibonacci-Zahl gibt.
Ein rekursiver Aufruf frisst Speicherplatz und Zeit! In Fällen, wo dies ausarten kann (wie hier - es wird einiges mehrfach berechnet, etc.), und es eine andere Möglichkeit (z. B. über Schleifen), ist es besser die andere Möglichkeit zu programmieren. Ich hab's getestet bei den Fibonacci-Zahlen. Der Unterschied ist enorm! Der Grund liegt beim Mehrfachaufruf von fibonacci(): einmal fibonacci(40), einmal fibonacci(39), zweimal fibonacci(38), dreimal fibonacci(37), fünfmal fibonacci(36), ...

Beschreibung | Beispiele

Perl, Lehrstuhl Mathe II, Uni Bayreuth