Rekursiv vs iterativ II

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]

Ackermann.om
PROCEDURE Ackermann(x, y: INTEGER) : INTEGER;
BEGIN
   IF x = 0 THEN
      RETURN y + 1
   ELSIF y = 0 THEN
      RETURN Ackermann(x - 1, 1)
   ELSE
      RETURN Ackermann(x - 1, Ackermann(x, y - 1))
   END;
END Ackermann;

*Es gibt berechenbare Funktionen, deren Rekursionstiefe sich nicht ohne die Berechnung derselben ermitteln läßt.
 
*Dazu gehört die obige Funktion von Wilhelm Ackermann in ihrer durch Rósa Péter und Raphael Robinson vereinfachten Form.
 
*Natürlich läßt sich die Ackermann-Funktion ohne den Selbstaufruf einer Prozedur lösen, aber dann muß die Rekursion ``per Hand'' nachprogrammiert werden.
 
*Mehr zum Unterschied zwischen primitiv rekursiven Funktionen (LOOP-berechenbar) und der allgemeineren Klasse der WHILE-berechenbaren Funktionen gibt es zum Beispiel im empfehlenswerten Buch von Uwe Schöning, ``Theoretische Informatik kurz gefaßt''.
 

 [Vorheriges Kapitel]  [Vorherige Seite]  [Inhaltsverzeichnis]  [Nächste Seite]  [Nächstes Kapitel]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999