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;

[Der_Unwissende]

Hey,
das ist doch mal ein Thread der mich interessiert :-D (für alle die nicht den Thread Theorie: Rekursive Funktion Abbrechen und Fortsetzen gelesen haben, ich bin der jmd (einer der?) der diese Behauptung aufgestellt hat)

Ok, ohne es jetzt zu überprüfen, geb ich dir mal Recht, dass ist der Algorithmus für die von-Neumann-Funktion in iterativ. Damit ist natürlich dieser Thread beendet (ausser jmd. traut an Beweis oder Gegenbeweis).
Aber

Zitat:

das nicht jede rekursive Funktion in ein iteratives Äquivalent überführt werden kann (was Quatsch ist)

es ist eben noch nicht gezeigt dass sich jede rekursive Funktion in eine iterative Überführen lässt.
Zugegeben, ich habe mich bisher immer auf Ackermann berufen, aber Ackermann ist halt nur eine von überabzählbar vielen rekursiven Funktionen. Es gibt halt schon überabzählbar viele Funktionen, die iterativ sind und jede iterative Funktion lässt sich erst recht in Rekursion überführen. Was hier aber eigentlich gesucht ist, ist eine Bijektion zwischen der Menge der rekursiven Funktionen und der Menge der iterativen Funktionen.
Sinnvollerweise kann man sich natürlich auf die wirklich (eben nicht nur durch ein CPU) berechenbare Funktionen beziehen (auch Turing-berechenbar oder intuitiv berechenbar genannt). Ok, jetzt fehlt hier für die (nur noch unendlich abzählbare Funktionen) die Bijektion. Das wäre ein Beweis. Ackermann könnte ja nur eine schlecht gewählte Funktion gewesen sein (ok, muss natürlich sagen, dass meine Unsicherheit stark auf dieser Funktion beruht hatte).
Ach ja, @alzaimar, im letzten Thread schrieb ich auch schon, dass ich mir nicht mehr sicher bin. Ich denke, dass es einen Beweis gab, der ganz klar zeigte ob es eine solche Bijektion gibt oder nicht, ich hab ihn halt nur nicht mehr in Erinnerung. Glaube eh, dass ich auch einen falschen Beweis akzeptieren würde (ist denke ich doch mal nicht mehr soweit her mit meinem Wissen in der TI).

Na ja, danke jedenfalls mal für die iterative Variante von Ackermann! :thumb: Und auch wenn sie nicht so elegant und hübsch ist, wie die rekursive Funktion, so kann ich trotz allem nur auf den geringeren Ressourcenbedarf verweisen. Oh man, da müsste ich eigentlich glatt mal gucken ob ich da nicht Lüge, hm, noch eine interessante Frage. Gibt es eigentlich einen Algorithmus, wo rekursiv deutlich sinnvoller (also rein auf Ressourcen bezogen) ist als iterativ?
Ich seh schon, auch hier kommt man schnell off topic.

Egal, hoffe jedenfalls, dass dir das Ruhe lässt, sonst würde ich mich noch schlecht fühlen, wenn du jedesmal 'ne Ewigkeit suchst, nur weil ich dumme (nicht haltbare) Thesen in den Raum schmeisse. Mein Name ist doch schließlich Programm

Also denne,
Gruß Der Unwissende

[alzaimar]

Zitat:

Zitat von Der_Unwissende

Aber

Zitat:

das nicht jede rekursive Funktion in ein iteratives Äquivalent überführt werden kann (was Quatsch ist)

es ist eben noch nicht gezeigt dass sich jede rekursive Funktion in eine iterative Überführen lässt.

Für Dich (und hier) vielleicht nicht. Ich hab mir einen Beweis ausgedacht, der darauf beruht, das ich ein Programm habe, das die Aufrufreihenfolge einer rekursiven Funktion zu festen Inputparametern erzeugt und diese iterativ abarbeitet, also einen Compiler und einen Interpreter.

Es gibt übrigens durchaus Verfahren, die diese Überführung automatisieren. Bei den Recherchen zu dem Ackermann stiess ich auf solch ein Verfahren (googel mal nach "Ackermann iterativ", etwas weiter hinten fangen dann die interessanten Skripte an).

Zitat:

Egal, hoffe jedenfalls, dass dir das Ruhe lässt, sonst würde ich mich noch schlecht fühlen, wenn du jedesmal 'ne Ewigkeit suchst, nur weil ich dumme (nicht haltbare) Thesen in den Raum schmeisse.

Mach mal nur weiter so :zwinker:. Ich mach hier sowieso nur, was mir Spass macht. :mrgreen:

Deine Skepsis ist übrigens sehr weit verbreitet. Sämtliche Skripte behaupten die Überführbarkeit jedes Rekursiven in einen iterativen Algorithmus. Fast alle Studenten glauben das nicht. Beweise sind dünn gesäht, fast so dünn wie iterative Achermännchen.

Zitat:

Also denne,

bis denne

Mark

[jim_raynor]

Das würde mich mal interessieren, wer behauptet, dass man nicht jede Funktion iterativ lösen kann. Natürlich kann man das. Die Rekursion unterstützt dich nur bei der Bildung eines Stacks und vereinfacht so die Speicherung der Variablen. Dieses müsstest du in einer iterativen Lösung einfach nur nachbilden (was zugegebener maßen nicht immer einfach ist). Aber ganz ehrlich. Die rekursive Variante finde ich wesentlich eleganter ;)

[Der_Unwissende]

Zitat:

Die Rekursion unterstützt dich nur bei der Bildung eines Stacks und vereinfacht so die Speicherung der Variablen

Mag ja sein, aber das ist doch gar nicht das worum es geht. Die Frage ob sich jeder rekursive Algorithmus auch iterativ lösen lässt kann nur für ein sehr allgemeines Rechnermodell beantwortet werden. Also müsste schon jmd. den konkreten Beweis antreten, dafür gäbe es wohl viele Wege

1) Für jeden (der überabzählbar vielen) Algorithmen ein iteratives Pendant aufzeigen - natürlich unmöglich
2) Eine Turingmaschine bauen, die rekursive Algorithmen in iterative überführt (hier frage ich mich ob man sich dann noch auf berechenbare rekursive Funktionen beschränken muss? Schließlich würde die TM ja nur überführen und nicht das erzeugte berechnen)
3) Die Einschränkung auf berechenbare Funktionen hinnehmen und dann nochmal zeigen (wurde definitv schon längst bewiesen), dass die Turing-Berechenbaren Funktionen oder (nach Church) die Menge der intuitiv berechenbaren Funktionen Äquivalent ist zu der Menge der Nü-Rekursiven Funktionen (da hätten wir natürlich auch Ackermann drin).

3) ist mir während unserer Diskussion einfach mal nicht eingefallen, aber eigentlich ist es das (für total rekursive Funktionen) doch schon. Denn alle diese Funktionen sind nach der (unbewiesenen) Churchen These iterativ durch die Turingmachine berechenbar. Und ich weiß noch, dass irgendwer gezeigt hat, das Lambda-Kalkül, Nü-Rekursive-Funktionen (Primitiv-Rekursiv + Ackermann) und Turingberechenbar gleichmächtig sind (und es eine paarweise Bijektion gibt).
Ja, ist natürlich sehr Argumentativ und immer noch kein Beweis, aber hier stösst man ja auch an das Problem, welche Funktionen überhaupt intuitiv berechenbar sind. Ich glaube es gibt weder einen Beweis, noch ein Gegenbeispiel für die Churche These, aber das machts ja nicht leichter.
Das es Algorithmen gibt, die jedes Programm (das für und auf einem PC u.ä. entwurfen wurde) ist klar, aber es ging ja um allgemeingültig. Werd mir vielleicht wirklich mal die Beweise durch googlen anschauen oder irgendwie mal wieder an ner Uni nen Prof der TI fragen oder so. Hm, hab doch noch irgendwo den Cormen, ob da auch was drin war zu dem Thema? :gruebel:
Na ja, irgendwo wird sich schon was dazu finden lassen.

[mschaefer]

N´abend

Zitat:

Zitat von jim_raynor

Das würde mich mal interessieren,
wer behauptet, dass man nicht jede Funktion iterativ lösen kann. Natürlich kann man das.

Ja das würde ich behaupten.
1. Das ist immer dann nicht möglich, wenn die Funktionen in einem Wertebereich nicht definiert sind.
-> Iteration lauft in eine undefinierten Bereich und bricht ab <- Fehler

2. Dann wenn Funktionen über Wertebereiche immer den gleichen Wert liefern, also nicht stetig sind.
Zum Beispiel bei sogeanannten Treppenfunktionen.
-> Im ungünstigsten Fall läuft die Iteration sich fest <- hört nie auf
-> Im wenig günstigen Fall läuft sie sehr langsam bis zur Lösung

Nun allgemeine Funktionssolver sind eine mathematisch doch recht komplexe Materie, das braucht Zeit.
Tja nun weist Du wer (einer davon), hilft Dir aber wahrscheinlich nicht wirklich weiter...

Grüße // Martin

[alzaimar]

Ich glaub, er meint 'rekursive Funktion/Prozedur'.
Ansonsten hast Du natürlich Recht. Viele Funktionen sind nicht iterativ lösbar, weil sie einfach nicht lösbar sind.

[mschaefer]

Ok, dann ist das korrekt, letzlich ist die Rekursion lediglich eine Verfahrensweise der Iteration. Tja Mark, Du hast da ja ein interessantes Hobby. Da gibt es bestimmt bald Gelegenheit sich mit Hagen über mathematische Algorithmen auszutauschen, sozusagen in der "Knobelelite" !

Schönes Wochenende Euch // Martin

[Phoenix]

Also.. Fakt ist, das jede Rekursive Funktion auch Iterativ lösbar ist. Das ist sogar mathematisch bewiesen worden, ich hab die Quelle nur nicht zur Hand. Werde aber am Montag gleich meinen Prof fragen, der wird wissen wo das steht. (Oder, was wahrscheinlicher ist, mir einen Tip geben wie ich es selber beweisen soll... :?).

Was im Allgemeinen dazu auch gilt: Die Rekursive Lösung ist in der Regel eleganter und einfacher, die Iterative in der Regel performanter weil nicht so Stack-Lastig und dadurch besser optimierbar.

[alzaimar]

Zitat:

Zitat von mschaefer

... Du hast da ja ein interessantes Hobby. ...

Einerseits Hobby, andererseits Beruf. Es ist einfach eminent wichtig, über Algorithmen, Möglichkeiten ('Was geht?'), NP-komplette Probleme, Suchverfahren etc. zumindest eingermassen Bescheid zu wissen. Bedauerlicherweise liegt der Schwerpunkt in dem Informatikstudium nicht hier. Das merke ich, wenn Studenten oder Berufsanfänger ein Subsystem implementieren sollen, und bei Suchverfahren grundsätzlich durchiterieren. Die haben noch nie was von Binary Search oder Hashtabellen gehört. Oder irgendwas dämlicherweise rekursiv implementieren und sich dann wundern, wenn ihnen der Stack um die Ohren haut.

So wie der Maschinenbauer das Grundhandwerk beherrschen sollte, muss das ein Informatiker auch.

Zurück zum Thema:
Ich hab mal eine iterative Quicksortvariante geschrieben, weil ich es einfach mal wissen wollte (so wie beim Ackermännchen):
Bei kleinen N ist die rekursive Implementierung doch schneller, bei großen N die Iterative.

[Robert Marquardt]

Es gilt nicht nur das jeder rekursive Algorithmus ein iteratives Aequivalent hat, sondern auch umgekehrt.
Der Beweis kann einfach ueber eine von-Neumann-Maschine gefuehrt werden.
Die von-Neumann-Maschine ist vollstaendig, sprich es koennen alle Algorithmen auf ihr implementiert werden.
Jeztz muss nur in einer rein rekursiven (Lisp) und in einer rein iterativen (z. B. Pascal Subset) Sprache eine von-Neumann-Maschine implementiert werden und fertig ist der Beweis.

Ich stelle fest das ich in den Achzigern der Studiengang Informatik besser war.
Ich lege allen Anfaengern Compilerbau ans Herz, damit man in voller Konsequenz begreift was XML eigentlich ist.

[glkgereon]

Zitat:

Zitat von Robert Marquardt

Ich lege allen Anfaengern Compilerbau ans Herz, damit man in voller Konsequenz begreift was XML eigentlich ist.

Gerne. Hast du ein Tipp für ein Buch oder ähnliches?

(Ich hab hier die "Praxisorientierte Einführung in den Compilerbau" von Baeumle und Alenfelder...aber die finde ich doch noch etwas abgehoben...)

[Der_Unwissende]

Zitat:

Es gilt nicht nur das jeder rekursive Algorithmus ein iteratives Aequivalent hat, sondern auch umgekehrt.

Stand nie zur Debatte, der umgekehrte Weg, also iterativ -> rekursiv ist ja schließlich trivial. Aber (auch das wurde schon erörtert),

Zitat:

Jeztz muss nur in einer rein rekursiven (Lisp) und in einer rein iterativen (z. B. Pascal Subset) Sprache eine von-Neumann-Maschine implementiert werden und fertig ist der Beweis

stimmt so natürlich überhaupt nicht. Es fehlt a) der Beweis, dass dein Von-Neumann-Rechner vollständig ist und natürlich dass du mit Lisp und dem Pascal Subset jeden Algorithmus implementieren kannst.
Ansonsten kann ich auch einfach sagen, dass es keine NP vollständigen und damit natürlich auch keine NP schweren Probleme mehr gibt, denn ein Quantencomputer hat gleichzeitig 0 und 1 in jedem Qubit stehen. Ist aber kein Beweis (der echte Beweis ob NP <> P ist, ist immerhin mit 10000$ dotiert, eins der 10 schwersten mathematischen Probleme).

Grundsätzlich kann man jedenfalls mit Beweisen, die auf einem Rechnermodell aufbauen nur maximal zeigen, dass etwas gleichmächtig mit dem Rechnermodell ist. Wenn du also sagst, dass jeder Algorithmus sich sowohl rekursiv als auch iterativ lösen lässt, so stimmt das nur für berechenbare Algorithmen. Ist jetzt sicher Definitionssache, ob man etwas was nicht berechenbar ist noch als Algorithmus durchgehenlassen kann oder nicht. Aber wenn es ein Problem gibt, dass sich iterativ formulieren lässt, jedoch als nicht berechenbar gilt, dann musst du auch dafür zeigen, wie man es in rekursion überführt. Das eigenltiche Problem ist und bleibt eigentlich nur diese Bijektion. Wenn also jmd. einen Algorithmus postet, der zeigt wie man deterministisch eine Funktion die Rekursiv ist in eine Iterative überführt und natürlich die Umkehrabbildung, dann ist das ein eideutiger Beweis (und der dürfte etwas weniger trivial sein als einfach über CPU oder Rechnermodell zu sprechen). Andere Ansätze sind (meiner Ansicht nach) weiterhin, sich auf berechenbare Probleme (total rekursive) zu beschränken. Da lässt ja schon der Name total rekursiv vermuten, dass sich all die Probleme rekursiv lösen lassen, die Frage ist dann halt ob es genau so iterativ gilt.

Zu den Dingen wie

Zitat:

So wie der Maschinenbauer das Grundhandwerk beherrschen sollte, muss das ein Informatiker auch.

möchte ich auch noch was sagen, kommt aber in neuen Beitrag.

[Flocke]

Zitat:

Zitat von alzaimar

Zurück zum Thema:
Ich hab mal eine iterative Quicksortvariante geschrieben, weil ich es einfach mal wissen wollte (so wie beim Ackermännchen):
Bei kleinen N ist die rekursive Implementierung doch schneller, bei großen N die Iterative.

Bei der ganzen Diskussion fehlt mir zunächst einmal die Definition: "was ist rekursiv?"

Sicher kann ich Quicksort ohne eigenen Funktionsaufruf hinschreiben, indem ich von den zwei Teilsegmenten einen auf einen Stack lege und mit dem zweiten direkt weitermache. Nichtsdestotrotz ist der Algorithmus rekursiv, denn das Problem wird dadurch gelöst, dass man auf zwei kleinere Teilabschnitte dasselbe Verfahren anwendet. Ob ich das nun über den CPU-Stack löse (Aufruf) oder den Stack selbst implementiere ändert nichts an der Verfahrensweise des Algorithmus.

Du (aber nicht alleine) hattest in dem anderen Thread ja mal als Beweis angeführt, dass eine CPU immer iterativ arbeitet und somit, sofern jeder rekursive Algorithmus implementiert werden kann, die Übersetzung in eine (iterative) Maschinensprache beweist, dass er iterativ ausgeführt werden kann. Ich hatte dann ja eine kleine rekursive Assemblerroutine hingeschrieben.

Allerdings ist es hier doch nur eine Schreibweise. Einen Unterschied darin zu sehen, ob eine Routine sich mit "call" selbst aufruft oder die Werte mit "push" auf den Stack legt und dann mit "jmp" wieder zum Start springt, ist doch eigentlich Haarspalterei.

Zurück zum Thema: für mich kommt es also nicht auf die Implementierung an sondern auf die Funktionsweise. Und hier ist jeder Algorithmus rekursiv, der nach "Divide and Conquer" verfährt und zur Lösung des Problems wieder den Algorithmus selbst auf Teilbereiche anwendet.

(los, zerreisst mich :mrgreen: )

[Robert Marquardt]

Zitat:

Zitat von Der_Unwissende

stimmt so natürlich überhaupt nicht. Es fehlt a) der Beweis, dass dein Von-Neumann-Rechner vollständig ist und natürlich dass du mit Lisp und dem Pascal Subset jeden Algorithmus implementieren kannst.

a) muss man in weiterfuehrender Literatur nachschlagen.
Das ich fuer Lisp oder das Pascal-Subset etwas beweisen muss ist hingegen nicht noetig.
Die implementierte Maschine fuehrt ja eine eigene Sprache aus.
Die Paarung rekursive Maschine mit beliebigem Programm ist rekursiv und die Paarung iterative Maschine mit beliebigem Programm ist iterativ.
Dafuer ist halt das Studium da. Man muss sich mit hoeherer Mathematik beschaeftigen.

[brechi]

Muss Flocke auch zustimmen.
Durch Hilfe mit einem Stack kann man sehr wohl die meisten (alle) rekursiven Funktionen in iterative umprogrammieren. Aber vielleicht sollte man mal schaun wie rekursiv und iterativ definiert sind. Hab jetzt nicht nachgeschaut aber für mich ist iteraritv wenn das Problem in kleine Teilprobleme zerlegt wird und diese nacheinander bearbeitet werden, und rekursiv wenn man vorherige berechnungen später wieder aufnimmt, also verschachtelt. D.h. form man einen rekursiven Alg in einen iterariven mit hilfe eines eigenen Stacks durch, bleibt er wie Flocke sagt in dem Fall rekursiv, auch wenn die eigentliche Funktion selbst nicht mehr aufgerufen wird.
Ist aber ein rekursiver Alg nur rekursiv wenn er sich selbst aufruft, dann kann man den immer mit einem eigenen Stack in einen iterativen umwandeln.

[Phoenix]

Zitat:

Zitat von Der_Unwissende

Zitat:

Zitat:

Zitat von Robert

Jeztz muss nur in einer rein rekursiven (Lisp) und in einer rein iterativen (z. B. Pascal Subset) Sprache eine von-Neumann-Maschine implementiert werden und fertig ist der Beweis

stimmt so natürlich überhaupt nicht. Es fehlt a) der Beweis, dass dein Von-Neumann-Rechner vollständig ist und natürlich dass du mit Lisp und dem Pascal Subset jeden Algorithmus implementieren kannst.

Dem ist nicht so. Natürlich stimmt das.

Wir zäumen gerade das Pferd von der falschen Seite auf. Korrekt wäre es so:

Nehmen wir mal die grundlegenden Fakten der theoretischen Informatik zur Hand:
1.) Jeder Computer lässt sich durch eine Turing-Maschine simulieren.
2.) Was nicht mit einer Turing-Maschine lösbar ist ist mit einem Rechner nicht lösbar (siehe Halteproblem).
3.) Eine Turing-Maschine kann nur folgendes: Lesen, Schreiben und den Kopf auf dem Band um ein(!) Feld bewegen.

Das bedeutet schonmal: Mächtiger als eine universelle Turing-Maschine geht mit einem Computer nicht. Aus Punkt 3 ergibt sich schlussendlich, dass eine Turing-Maschine ausschliesslich iterativ vorgehen kann (sie erlaubt keinerlei Sprünge).

Oder andersrum: Jede Turing-Vollständige Programmiersprache ist gleich mächtig. Das bedeutet das eine Turing-Vollständige Programmiersprache die keine Rekursion kennt gleich mächtig ist wie eine, die Rekursion kennt. Das bedeutet beide können das gleiche Leisten und das heisst jede Rekursion muss auch Iterativ lösbar sein (Ob man eine Lösung findet oder gar ohne Brute-Force finden kann ist eine andere Sache, aber es muss zumindest eine geben).

Es gibt dann weiterhin Beweise dass sich alle Turing-Programme auch in GOTO-Programmierung (also mit dem 'Feature' von Sprüngen, das die Turing-Maschine nicht bietet) lösen lassen und umgekehrt. Weiterhin ist dann bewiesen dann GOTO-Programme auch WHILE-Berechenbar sind und umgekehrt und so baut sich dann Stück für Stück der Umfang der heutigen Programmiersprachen auf.

[Robert Marquardt]

Turing nicht von Neumann. Der Mann hat recht.

Meine Argumentation geht so:
Die Menge der Turingprogramme umfasst alle Programme.
Die Menge der Tupel Turingprogramm und iterativ implementierte Turingmaschine ist offensichtlich gleichmaechtig und iterativ.
Die Menge der Tupel Turingprogramm und rekursiv implementierte Turingmaschine ist offensichtlich gleichmaechtig und rekursiv.
Mithin ist der Beweis angetreten das alle Programme rekursiv und iterativ implementiert werden koennen. Allein durch die Wahl der ausfuehrenden Turingmaschine.

[kopernikus]

Der im ersten Beitrag angegebene Quelltext für die iterative Berechnung der Ackermann-Funktion enthält noch einen kleinen Fehler, der sich allerdings nur bei j=m=0 auswirkt. Es fehlt eine Initialisierung des Arrays place auf -1.

Mit ein paar Schönheitskorrekturen muss es heißen:

Delphi-Quellcode:

function ack (n,m : int64): int64;
var
   value,place : array of int64;
   k : integer;
begin
  result:=0;
  if n=0 then result:=m+1
  else begin
    setlength(value,n+1);
    setlength(place,n+1);
    for k:=0 to n do place[k]:=-1;
    value[0]:=1;
    place[0]:=0;
    repeat
      inc(max);
      inc(value[0]);
      inc(place[0]);
      for k:=0 to n-1 do begin
        if place[k]=1 then begin
          value[k+1]:=value[0];
          place[k+1]:=0;
          if k<>n then break;
          end
        else begin
          if place[k]=value[k+1] then begin
            value[k+1]:=value[0];
            inc(place[k+1]);
            end
          else break;
          end;
        end;
      until place[n]=m;
    result:=value[0];
    end
  end;

[gammatester]

Zitat:

Zitat von kopernikus (Beitrag 1208073)

Der im ersten Beitrag angegebene Quelltext für die iterative Berechnung der Ackermann-Funktion enthält noch einen kleinen Fehler, der sich allerdings nur bei j=m=0 auswirkt. Es fehlt eine Initialisierung des Arrays place auf -1.

Was ist j? Bei Dir gibts das nicht. Meinst Du mit den Originalvariablen i=j=0? Der Fall ist aber behandelt mit

Delphi-Quellcode:

If i = 0 Then
    Result := j + 1

[DeddyH]

Vielleicht sollte man den Fall "n ist negativ" auch noch berücksichtigen.

[kopernikus]

Im Originalquelltext heißen die Parameter im Funktionsaufruf i und j. Der Fehler tritt auf wenn i>0 und j=0 ist. In meinem Quellcode habe ich die Parameter der Konvention entsprechend in n und m umbenannt, siehe auch den Artikel bei Wikipedia.
Für Werte n,m<0 ist die Funktion nicht definiert.