Claus Schönleber

Hitchhacker´s Guide To PASCAL  [Vol. 2]

Inhalt

Rekursion

Allerdings hat es wenig Sinn, mit Rekursionen zu argumentieren, die sich im Aufwand von Iterationen nicht unterscheiden lassen. Dann ist es wirklich nicht einzusehen, daß Rekursionen überhaupt benötigt werden.

In diesem Kapitel werden deshalb zwei Ansätze zur Rekursion aufgeführt:

1. Die üblichen Beispiele aus der Literatur zur Funktionsbeschreibung. Diese Beispiele könnten genausogut oder sogar besser iterativ formuliert werden, was auch demonstriert wird (Fakultät, Potenzieren).
2. Beispiele zur Rechtfertigung (Permutationen, Türme von Hanoi).

Was ist Rekursion?

1. Teil eins ist eine Anfangsbedingung
2. Teil zwei ist die Definition eines beliebigen Resultates aus seinen Vorgängern. Das klingt befremdlich, ist aber genial einfach. Zur Demonstration hier gleich ein Programm, das die Fakultät berechnet (Die Fakultät einer Zahl wird durch ein nachgestelltes "!" beschrieben).

        [  1, falls x = 0
x! :=  <   x * (x - 1)!, falls x > 0 
        [  nichts sonst

PROGRAM recursive1;

  VAR i : integer;

FUNCTION fak (x : integer) : integer;
BEGIN
  IF (x = 0) THEN
    fak := 1
  ELSE
    fak := x * fak (x - 1);
END;

BEGIN
  write ('Zahl: ');
  readln (i);
  writeln (i,'! = ',fak (i));
END.

• Ist die eingegebene Zahl in "i" eine 0, dann ist alles klar. Das Ergebnis heißt 1.
• Für jede höhere Zahl, zum Beispiel 3, geht das Verfahren so:
• fak (3) ist dasselbe wie 3 mal fak (2).
• fak (2) ist dasselbe wie 2 mal fak (1).
• fak (1) ist dasselbe wie 1 mal fak (0).
• fak (0) ist gleich 1.
• fak (1) ist gleich 1 mal 1 gleich 1.
• fak (2) ist gleich 2 mal 1 gleich 2.
• fak (3) ist gleich 3 mal 2 gleich 6.
• Fertig!

Rekursion

Rekursion ist ein Verfahren, einen zu berechnenden Wert auf die Definition seines Vorgängers zurückzuführen. Ein Anfangswert muß definiert sein, um das Verfahren kontrolliert enden zu lassen. Eine rekursive Funktion ruft sich selbst auf, direkt oder indirekt über eine Zwischenfunktion.

Beispiele

Obiges Programm "Fakultät", folgende Beispiele.

x! := 1 * 2 * 3 * ... * x

PROGRAM fak_it;
  VAR x,i,f : integer;
BEGIN
  write ('Zahl: ');
  readln (x);
  f := 1;
  FOR i := 1 TO x DO
    f := f * i;
  writeln (x,'! = ',f);
END.

       [  1, falls y = 0
xy := <   x * x(y - 1),falls y > 0 
       [  nichts sonst

PROGRAM recursive2;

  VAR x,y : integer;

FUNCTION power2 (base,exponent : integer) : integer;
BEGIN
  IF exponent = 0 THEN
    power2 := 1
  ELSE
    power2 := base * power2 (base,exponent - 1);
END;

BEGIN
  write ('Basis und Exponent eingeben: ');
  readln (x,y);
  writeln ('Ergebnis: ',power2 (x,y));
END.

Um Ihnen trotzdem einen Vorgeschmack zu geben, wie schwierig manche Probleme werden, wenn man keine Rekursion einsetzen darf, soll zunächst das Problem und dann ein Programmvorschlag besprochen werden.

Stellen Sie sich eine Liste vor, zum Beispiel
 

Die soll jetzt durch Vertauschen beliebiger Elemente in allen möglichen Kombinationen angeordnet werden. Das sieht dann so aus:

1 2 3
1 3 2
2 3 1
2 1 3
3 1 2
3 2 1

Zum Verfahren: die Grundoperation ist das Rotieren einer Liste, wie man an obigem Beispiel leicht nachvollziehen kann. Das wird in der Prozedur "rotate" erledigt. In "permute" wird die Ausgabe auf dem Bildschirm und das Rotieren der aktuellen Unterliste vorgenommen. Die zu permutierende Liste ist in "liste" als String untergebracht.

PROGRAM permutations;

  USES crt;

  TYPE str = STRING [80];

  VAR list : str;
      max  : integer;

PROCEDURE rotate (VAR _rlist : str; _len : integer);
  VAR i : integer;
      c : char;
BEGIN
  c := _rlist [1];
  FOR i := 1 TO _len DO
    _rlist [i] := _rlist [i + 1];
  _rlist [_len] := c;
END;

PROCEDURE permute (VAR result : str; len : integer);
  VAR i : integer;
BEGIN
  IF (len = 1) THEN
  BEGIN
    FOR i := 1 TO max DO
      write (result [i]:5);
    writeln;
  END
  ELSE
    FOR i := 1 TO len DO
    BEGIN
      rotate (result,len);
      permute (result,len - 1);
    END;
END;

BEGIN
  clrscr;
  list := '123456';
  max := length (list);
  permute (list,max);
END.

Als Bonbon noch zwei Programme, die Sie als Denksportaufgaben betrachten können.

Ackermann

Die Funktion ruft sich nicht nur einfach selbst auf, sondern auch als Parameter von sich selbst. Das nachzuvollziehen stellt schon eine Herausforderung an die eigene geistige Beweglichkeit dar!

PROGRAM ackermann;

  VAR m,n,o,x : integer;

FUNCTION ack (n,m : integer) : integer;
BEGIN
  x := x + 1;
  IF (n = 0) THEN
    ack := succ (m)
  ELSE
    IF (m = 0) THEN
      ack := ack (pred (n),1)
    ELSE
      ack := ack (pred (n),ack (n,pred (m)));
END;

BEGIN
  x := 0;
  writeln ('Ackermann-Funktion');
  write (' Geben Sie zwei Zahlen ein : ');
  readln (m,n);
  writeln;
  o := ack (m,n);
  writeln;
  writeln ('ACK (',m,',',n,') = ',o);
  writeln ('Aufrufe : ',x)
END.

ack (1,1) = 3 (4 Aufrufe)
ack (2,2) = 7 (27 Aufrufe)
ack (2,3) = 9 (44 Aufrufe)
ack (3,3) = 61 (2432 Aufrufe)
ack (3,4) = 125 (10307 Aufrufe)

ack (4,2) besitzt 19729 Stellen
ack (4,4) ist größer als 10 hoch 10 hoch 10 hoch 19000 

McCarthy

IF x > 100 THEN 
  x := x - 10
ELSE 
  x := 91;

PROGRAM mccarthy (input,output);

  VAR x : integer;

PROCEDURE p (VAR s : integer);
BEGIN
  IF s > 100 THEN
    s := s - 10
  ELSE
  BEGIN
    s := s + 11;
    p (s);
    p (s)
  END
END;

BEGIN
  write ('ZAHL : ');
  readln (x);
  p (x);
  writeln (x)
END.

Türme von Hanoi

Dabei gelten folgende zwei Regeln:

• Es darf immer nur eine Scheibe bewegt werden.
• Es darf immer nur eine kleinere Scheibe auf einer größeren liegen, nie umgekehrt.

PROGRAM towers_of_hanoi;

PROCEDURE hanoi (n,ap,zp : integer);
BEGIN
  IF (n > 1) THEN
    hanoi (n - 1,ap,6 - ap - zp);
  write ('Scheibe ',n,' von Turm ',ap,' nach Turm ',zp);
  IF (n > 1) THEN
    hanoi (n - 1,6 - ap - zp,zp);
END;

BEGIN
  (* Beispielaufruf fuer 5 Scheiben, von Turm 1 nach Turm 3 *)
    hanoi (5,1,3);
END.