int fak(int i) {
if (i==0) return 1;
else return fak(i-1)*i;
}
Nur, wenn Du Stacks zuläßt. Siehe oben. Eine Rekursion basiert immer auf einem Stack. In diesem Fall (Ackermannfunktion) wird mit dem Stack die Rekursion nachgebildet. Somit ist, nach meinem Dafürhalten immer noch rekursiv gelöst.Prinzipiell läßt sich jedes Problem, das man rekursiv lösen kann, auch iterativ lösen.
Ein Stack ist eine normale Datenstruktur, wie es noch eine Vielzahl andere gibt - warum sollte man diese auch verbieten?Nur, wenn Du Stacks zuläßt.
Und eine Schleife immer auf einer Schleifenvariable. Ist demnach bei einer Rekursion kein Variablenzugriff erlaubt, weil Schleifen darauf basieren?Eine Rekursion basiert immer auf einem Stack.
Dann hast du eine falsche Definition von Rekursion. Die Essenz einer rekursiven Funktion (man beachte! Es muss sich um eine Funktion handeln - das hat mit dem obigen Schleifenkonstrukt schonmal gar nix zu tun) ist, dass sie sich selbst aufruft.In diesem Fall (Ackermannfunktion) wird mit dem Stack die Rekursion nachgebildet. Somit ist, nach meinem Dafürhalten immer noch rekursiv gelöst.
Das hatten wir alles schon. Nur weil die Funktion sich nicht explizit selbst aufruft, wird daraus immer noch keine iterative Funktion.Ein Stack ist eine normale Datenstruktur, wie es noch eine Vielzahl andere gibt - warum sollte man diese auch verbieten?
In diesem Beispiel ist die Rekursion zum Beispiel schlecht da sie nicht endrekursiv implementiert ist. Mit einem Akku is das gleich viel besser!
Nur, wenn Du Stacks zuläßt. Siehe oben. Eine Rekursion basiert immer auf einem Stack. In diesem Fall (Ackermannfunktion) wird mit dem Stack die Rekursion nachgebildet. Somit ist, nach meinem Dafürhalten immer noch rekursiv gelöst.
sorry, aber was willst du damit sagen. dass die funktion - obwohl sie sich nicht explizit und auch nicht implizit selbst aufruft - eine rekursive funktion sein soll?Das hatten wir alles schon. Nur weil die Funktion sich nicht explizit selbst aufruft, wird daraus immer noch keine iterative Funktion.
hust. ähh, was war denn das, was ich oben gemacht habe? eine iterative variante von ackermann oder nicht? und dann, weil du bei deinem standpunkt von stack unvereinbar mit iterativ bliebst, eine iterative variante von stack oder nicht? irgendwo ein fünkchen rekursion?Im Gegensatz zu Fakultät, die Du sowohl rekusiv ( f(1)=1 ; f(n)=n*f(n-1) ), als auch iterativ ( f(n)= Prod[i=1..n](i) ) definieren kannst, wird Dir eine rein iterative Definition der Ackermann Funktion nicht gelingen.
ok, dann erklär du uns mal deine begrifflichkeit - mir scheint nicht, dass einer von uns das ganze nicht begriffen hat, sondern dass wir uns auf grundlegend unterschiedliche begriffe bezüglich primitive rekursion, µ-Rekursion und Iteration stützen.Bevor Du Dich weiter darüber ausläßt, versuch doch bitte zunächst mal den Begriff der primitive Rekursivität zu verstehen.
ähh, endrekursion hat nichts mit abbruch-bedingung zu tun. endrekursion bedeutet, dass jeder rekursionsschritt in sich abgeschlossen ist und nicht auf ergebnisse tieferer rekursionsebenen warten muss - so dass man bei grösseren berechnungen nicht einen cray nur für den stack einschalten muss.Du siehst die Abbruchbedingung (i==0) nicht?
full ack - wie ich oben mal gepostet habe: rekursive ansätze sind meist eleganter und oft intuitiver als iterative ansätze. mit endrekursion sind sie oft nicht mal weniger effizient als iterationMag sein. Mir ging es darum, den iterativen Ansatz in Punkto Einfachheit zu schlagen.
Du siehst die Abbruchbedingung (i==0) nicht?
Sie ist rekursiv, auch wenn sie nicht so aussieht. Alleine dadurch, wie Du den Stack verrwendest:hust. ähh, was war denn das, was ich oben gemacht habe? eine iterative variante von ackermann oder nicht?
Alleine dadurch, daß Du den expliziten rekursiven Aufruf kaschierst, wird es nicht nicht-rekursiv. Vergleiche auch http://www.mathematik.uni-ulm.de/sai/ss99/prog/skript/rekursion-07.htmlCode:INPUT (x,y); INIT (stack); PUSH (x, stack); PUSH (y, stack); WHILE size(stack) != 0 DO { # Müßte das nicht 1 sein? y:= POP(stack); x:= POP(stack); # Hier holst Du die Argumente für a vom Stack IF x=0 { THEN PUSH(y+1, stack); # Hier schiebst Du das Ergebnis auf den Stack } ELSEIF y=0 { THEN PUSH(x-1, stack); # Hier schiebst Du die veränderten PUSH(1,stack); # Ausgangswerte wieder auf den Satck # Im Prinzip ließe sich bis hierher alles ohne Rekursion und # somit auch ohne Stack lösen } ELSE { PUSH(x-1, stack); # Hier schiebst Du einen Parameter auf den Stack # der erst sehr viel später wieder verwebdet wird. # Dies ist vom Prinzip her eine Rückkehradresse PUSH(x, stack); # Hier kommen 2 Werte auf den Stack PUSH(y-1, stack); # Dieser Teil ginge auch noch ohne Rekursion # Durch den einen zusätzlichen Wert ersetzt Du den explizite # rekursiven Aufruf. } } result := POP(stack) OUTPUT(result)
Naja... Dann schaust Du vielleicht nicht richtig hin.Was jetzt allerdings den Umbau einer rekursiven Funktion zu einer iterativen unter Zuhilfenahme eines Stacks betrifft, so erkenne ich in der iterativen Variante keine Rekursion, auch wenn vielleicht irgendwelche Ähnlichkeiten da sein können.
Dem würde ich auch widersprechen.Aus deiner Darstellung könnte man fast schlussfolgern, dass immer wenn ein Stack zum Einsatz kommt, es sich um Rekursion handelt und dem möchte ich doch widersprechen.
Skeeve schrieb:In diesem Fall ist es so, daß eine Schleife immer wieder läuft, aber mit Hilfe eines Stacks Zwischenstände speichert um später an der Stelle weiterarbeiten zu können.
Das Problem ist einfach, daß es für die Ackermann Funktion nun mal keine Nicht-rekursive Definition gibt. Und mit "Definition" meine ich hier die mathematische Bedeutung. Nicht etwa irgendwelche Repräsentationen als Programm. Ackermann ist nun mal so definiert, daß ein Ergebnis auf anderen Ergebnissen aufgebaut ist.Ich verstehe schon was du meinst, aber ich würde nicht soweit gehen und behaupten, dass es sich immernoch um eine Rekursion handelt.
Wir verwenden essentielle Cookies, damit diese Website funktioniert, und optionale Cookies, um den Komfort bei der Nutzung zu verbessern.
Für die Ihnen angezeigten Verarbeitungszwecke können Cookies, Geräte-Kennungen oder andere Informationen auf Ihrem Gerät gespeichert oder abgerufen werden.
Anzeigen und Inhalte können basierend auf einem Profil personalisiert werden. Es können mehr Daten hinzugefügt werden, um Anzeigen und Inhalte besser zu personalisieren. Die Performance von Anzeigen und Inhalten kann gemessen werden. Erkenntnisse über Zielgruppen, die die Anzeigen und Inhalte betrachtet haben, können abgeleitet werden. Daten können verwendet werden, um Benutzerfreundlichkeit, Systeme und Software aufzubauen oder zu verbessern.
Durch das Klicken des Buttons "Zustimmen" willigen Sie gem. Art. 49 Abs. 1 DSGVO ein, dass auch Anbieter in den USA Ihre Daten verarbeiten. In diesem Fall ist es möglich, dass die übermittelten Daten durch lokale Behörden verarbeitet werden.