RekursionPerl

SeitenanfangSeitenendeBeschreibung

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.

SeitenanfangSeitenendeBeispiele

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
  }
}

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:

  1. Bestimme alle Files und Unterverzeichnisse im Verzeichnis.
  2. Gebe die Files aus.
  3. 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);
  }
}

Seitenanfang FehlermeldungHilfe zur Fehlermeldung © 2001-2003 Email an den AutorPerl, Lehrstuhl Mathe II, Uni Bayreuth