Ich habe in einem algorithmischen Buch gelesen, dass die Ackermann-Funktion nicht tail-rekursiv gemacht werden kann (was sie sagen ist "es kann nicht in eine Iteration umgewandelt werden"). Ich bin ziemlich verblüfft darüber, also habe ich es versucht und es mir ausgedacht:
%Vor%(es ist OCaml / F # code).
Mein Problem ist, ich bin mir nicht sicher, ob das tatsächlich tail rekursiv ist. Kannst du bestätigen, dass es so ist? Wenn nicht, warum? Und schließlich, was bedeutet es, wenn Leute sagen, dass die Ackermann-Funktion nicht primitiv rekursiv ist?
Danke!
Ja, es ist tail-rekursiv. Jede Funktion kann durch eine explizite Umwandlung in Continuation Passing Style in tail-rec umgewandelt werden.
Dies bedeutet nicht, dass die Funktion im konstanten Speicher ausgeführt wird: Sie erstellen Stapel von Fortsetzungen, die zugewiesen werden müssen. Es kann effizienter sein, die Fortsetzungen zu defunktionalisieren , um diese Daten als einfachen algebraischen Datentyp darzustellen.
primitive rekursive ist ein ganz anderer Begriff, der sich auf die Ausdruckskraft einer bestimmten rekursiven Definition bezieht, die in mathematische Theorie, aber wahrscheinlich nicht sehr relevant für die Informatik, wie Sie es kennen: sie sind von sehr reduzierter Ausdruckskraft, und Systeme mit Funktionszusammensetzung (beginnend mit Gödel System T), wie alle aktuellen Programmiersprachen, sind viel mächtiger / p>
In Bezug auf Computersprachen entsprechen primitive rekursive Funktionen ungefähr denen ohne allgemeine Rekursion, wobei alle Schleifen / Iterationen statisch begrenzt sind (die Anzahl der möglichen Wiederholungen ist bekannt).
Ja.
Jede rekursive Funktion kann per Definition in eine Iteration umgewandelt werden, solange sie Zugriff auf ein ungebundenes stack-like-Konstrukt hat. Die interessante Frage ist, ob es ohne einen Stack oder einen anderen unbegrenzten Datenspeicher möglich ist.
Eine tailrekursive Funktion kann nur dann in eine solche Iteration umgewandelt werden, wenn die Größe ihrer Argumente beschränkt ist. In Ihrem Beispiel (und fast jeder rekursiven Funktion, die Fortsetzungen verwendet) ist der Parameter cont für alle Mittel und Zwecke ein Stapel, der auf jede Größe anwachsen kann. In der Tat besteht der ganze Punkt des Fortsetzungs-Übergabestils darin, Daten zu speichern, die normalerweise auf dem Aufruf-Stapel ("was zu tun ist, nachdem ich zurückkomme?") In einem Fortsetzungs-Parameter statt.
Tags und Links algorithm ocaml tail-recursion