Iterative Ackermannfunktion: Und sie gibt es doch (puh!)

[alzaimar]

Die Ackermannfunktion ist ein Paradebeispiel für die Eleganz der Rekursion und wird hier im Forum immer wieder gerne als Beispiel dafür genommen, das nicht jede rekursive Funktion in ein iteratives Äquivalent überführt werden kann (was Quatsch ist).

Das hat mir einfach keine Ruhe gelassen. Bevor ich nun die Lösung präsentiere, hier zunächst die 'klassische Defintion':

Delphi-Quellcode:

Function Ack(m, n: Integer): Integer;
Begin
  If m = 0 Then
    result := n + 1
  Else If n = 0 Then
    Result := Ack(m - 1, 1)
  Else
    Result := Ack(m - 1, Ack(m, n - 1))
End;

Sinn und Zweck dieser Funktion ist sehr gut im Wiki erklärt.

Und für Alle, die es nicht glauben wollten, ist hier eine rein iterative Variante, die ich... nee, nicht selbst entwickelt habe... sondern nach langem Suchen im Internet gefunden habe.
Sie stammt aus einem Artikel über die Programmiersprache ICON.

Delphi-Quellcode:

Function IconAckermann (i, j: Integer): Integer;
Var
  Value,
  Place : Array Of Integer;
  k : Integer;

Begin
  If i = 0 Then
    Result := j + 1
  Else Begin
    setLength(Value, i + 2);
    SetLength(Place, i + 2);
    Value[1] := 1;
    Place[1] := 0;
    Repeat
      inc(Value[1]);
      inc(Place[1]);
      For k := 1 To i Do Begin
        If Place[k] = 1 Then Begin
          value[k + 1] := value[1];
          place[k + 1] := 0;
          If k <> i Then Break;
        End
        Else Begin
          If place[k] = value[k + 1] Then Begin
            value[k + 1] := value[1];
            inc(Place[k + 1]);
          End
          Else
            Break;
        End;
      End;
      If Place[i + 1] = j Then Begin
        Result := Value[1];
        Exit
      End;
    Until False;
  End
End;