Rekursion als Schleifen darstellen (java)

[Jochen (Gast)]

Hallo,

ich suche nach einem Schema, um Rekursionen als Schleifen umzuschreiben.

Für

static void down1 (int n)
{
 if ( n <= 0)
  return;

System.out.println( n + ",");
down1( n - 1 );
}

habe ich schon gedacht:
1. If Answieung negieren und in die Bedingung der while schleife 
schreiben
2. Rekursionsaufruf n -1 zieht von n eins ab und macht damit alles von 
forne, ist also die Zählvariable der Schleife

das wäre dann  also:

while (n>0)
{ System.out.println ( n + ", ");
n = n - 1
}

Ist das so effektiv, wie würdet ihr das machen? Geht es so, dass man 
nicht negieren muss?

Wie würde das aussehen, wenn man in einer Rekursion 2 Rekusrsionsaufrufe 
hat:

static void down1 (auto auto)
{
 if ( n == 0 )
  return;
System.out.println(auto)
down1(auto.links)
down1(auto.rechts)
}

wie würde man das enstprechend umschreiben, hier fällt mir nichts zu 
ein...

Danke !

[Jochen (Gast)]

Zu meinem ersten Beispiel: mir fällt grad auf, dass die nicht äquivalent 
sind,
da der Wert von n nach der Rekursion gleich ist, bei der Schleife aber 
verändert ist.
Kann man das umschreiben, damit es wirklich gleich ist, ohne neue 
Variablen einzuführen?

[Jemand (Gast)]

>Ist das so effektiv, wie würdet ihr das machen? Geht es so, dass man
>nicht negieren muss?

Bis auf dass des öfteren ';' fehlt, sollte das funktionieren. Als 
effektiv würde ich auch nur die Schleife bezeichnen wollen.

Was willst du nicht negieren? Die Schleifenbedingung? Was sollte das 
bringen?
Wenn es nur um ein Schema geht, dann nimm halt 'while(!(n <= 0))'.

>Wie würde das aussehen, wenn man in einer Rekursion 2 Rekusrsionsaufrufe
>hat:

Hat man das? Meines Wissens nach nicht.
Weiter ist das Beispiel im speziellen sinnlos, da keine Variable 
mitübergeben wird, bzw. die Abbruchbedingung nicht zur Variablen passt.

Wenn man das wirklich iterativ darstellen wollte, so müsste man in einer 
Schleife jeweils den ersten Aufruf abarbeiten und danach in einer 
zweiten Schleife rückwärts den zweiten.
Vllt. einfach mal ne einfache Rekursion nach dem Beispiel aufstellen und 
durchspielen.

>Kann man das umschreiben, damit es wirklich gleich ist, ohne neue
>Variablen einzuführen?

Die Rekursion oder die Schleife? Falls letzteres: Fiele mir jetzt nichts 
dazu ein. Allerdings ist zu erwähnen, dass die Rekursion haufenweise 
neue Variablen einführt, wieso sollte das die Schleife dann nicht auch 
dürfen?

Weiter müsste man sich auch überlegen, dass man die Schleife als 
Rekursionsersatz in eine Funktion packen sollte, denn dann sieht der 
Aufruf aus dem eigentlich Code heraus gleich aus, und das n des 
eigentlichen Codes ändert sich auch nicht.

[Karl H. (kbuchegg)]

Deine erste Rekursion ist von einer speziellen Gestalt: Tail-Rekursion.
Sowas lässt sich immer in eine Schleife umwandeln. Ob dein
vorgeschlagenes Schema immer funktioniert kann ich so auf
die Schnelle nicht sagen, klingt aber nicht schlecht.

Im Allgemeinenen, wenn ich mich recht erinnere, wird eine
Rekursion so in eine iterative Lösung umgeformt, indem man
einen Stack einführt auf dem die Rekursionsstufen samt
aktuellem Aufrufstatus zwischengelagert werden und sowas wie
eine Statemachine eingeführt wird, die die Ablaufsteuerung
beim 'rekrusiven return' übernimmt.
Im Prinzip ist diese Lösung daher immer noch rekursiv, nur macht
man dann selbst die Arbeit, die ansonsten der Compiler bzw. die
CPU mit ihrem Callstack macht.

Schön ist das aber nicht. Hab das mal vor Jahren auf der Uni
mit dem bekannten Hanoi-Beispiel gesehen:
Die rekursive Lösung war kurz, die iterative Lösung lang.
Von der Laufzeit her, waren beide gleich.

[yalu (Gast)]

Endrekursionen wie im ersten Beispiel löst man etwas allgemeiner
folgendermaßen auf:

1. Der gesamte Funktionsrumpf wird in eine Endlosschleife (for(;;)
   oder while(true)) gepackt.

2. Der rekursive Aufruf der Funktion in der letzten Zeile wird -
   zusammen mit einem evtl. davor stehenden return - weggelassen und
   die an die Funktion übergebenen Argumente explizit den
   Funktionsparametern zugewiesen.

Das ist alles. Ein oder mehrere bedingte Returns innerhalb der
Schleife stören nicht, sie tun das, was sie auch sollen. Wenn man
will, kann man natürlich nachträglich den entstandenen Code noch etwas
verschönern.

Viele Compiler lösen übrigens Endrekursionen automatisch auf. So bspw.
der GCC, bei den meisten Funktionalsprachen muss das Compiler sogar
tun. Wie es mit Java aussieht, müsstest du mal ausprobieren.

Nicht-Endrekursionen, darunter auch Mehrfachrekursionen, können
mittels Kellerautomaten rekursionsfrei ausgeführt werden. Such mal
nach dem Begriff "Entrekursivierung", da gibt es ziemlich viel zu
lesen.

[Jochen (Gast)]

Ich danke für die vielen Antworten ;)
Könntet ihr mir dann vllt. mal schreiben, wie mein erstes Beispiel mit 
der Anleitung von yalu aussehen würde? Ich versteh das noch nicht 
richtig, und das ist genau das Rezept was ich gesucht habe :D

[yalu (Gast)]

Im Prinzip schon so ähnlich, wie du es beschrieben hast, nur mache ich
mir zunächst noch keine Gedanken zur Negierung von irgendwelchen
Bedingungen. Die bleiben erst einmal so stehen, wie sie sind und
werden höchstens im Rahmen von Schönheitskorrekturen geändert:

static void down1 (int n)
{
  while(true)
  {
    if ( n <= 0)
      return;

    System.out.println( n + ",");
    n = n - 1;
  }
}

[Jochen (Gast)]

OK, danke. Ich find das nämlich besser, wenn ich weiß, wie das "sauber" 
geht und nicht irgendetwas zusammenwürfel.

Wie macht man das, wenn eine Rekursion innerhalb einer Methode zweimal 
aufgerufen wird?

Als beispiel habe ich den Tiefendurchlauf von einem Baum:

public void inorder(ZahlNode node) {
    if (node == null) return ;
    inorder(node.left);
    do_something(node.z);
       inorder(node.right);

(Zur erklärung, node ist ein Objekt einer Klasse mit einem left, right 
Feld, wo der Verweis zum nächsten drin ist. z ist der Wert, der im 
Knoten gespeichert ist.)

[Christoph _. (chris)]

Eine Standard-Methode in der Theorie der Programmiersprachen ist das 
ganze in Continuation Passing Style umzuwandeln. Damit kann man jede 
rekursive Funktion durch relativ simple Regeln in eine endrekursive (und 
damit praktisch eine iterative) Funktion verwandeln. Das Problem ist 
nur, dass Continuation Passing Style in C++ nicht sonderlich gut 
funktioniert, da C++ keine Closures unterstuetzt.

Continuation Passing Style basiert auf dem Konzept der "Continuation". 
Eine Continuation ist ein Parameter einer rekursiven Funktion. Eine 
Continuation ist aber auch selbst eine Funktion, die anstelle return 
aufgerufen wird. Eine Continuation stellt "den Rest der Berechnung" dar, 
also alles das, was nach einem rekursiven Aufruf noch stattfinden soll.
Das grosse Ziel ist dabei rekursive Aufrufe in End-Position zu bringen. 
Daher fasst man alle Berechnungen, die "nach" dem rekursiven Aufruf 
stattfinden sollen, in ein Funktions-Objekt zusammen und uebergibt 
dieses beim rekursiven Aufruf.

Eine Simulation dieses Stils koennte in C++ zum Beispiel so aussehen 
(ungetestet):

struct Continuation {
  Continuation* next;
  Node* current;

  void eval() {
    if(current) {
      do_something(current);
      inorder(current->right, next);
    }
    else if(next)
      next->eval();
  };
};

void inorder(Node* root, Continuation* c) {
  if(!root)
    c->eval();
  else {
    Continuation c2 = { c, root };
    inorder(root->left, &c2);
  }
}

// aufgerufen wird das ganze so:
Continuation c = { 0, 0 };
inorder(root, &c);

Durch diese Umschreibung stehen saemtliche Aufrufe von rekursiven 
Funktionen nun am Ende, direkt beim return. Dadurch haben wir also eine 
end-rekursive Funktion bekommen.
Continuation Passing Style ist in Sprachen wie C++ allerdings ziemlich 
unueblich und umstaendlich.

In funktionalen Sprachen wie Haskell geht das ganze viel eleganter. 
Zuerst die klassische rekursive Variante:

inOrder :: Node -> m ()
inOrder Empty = return ()
inOrder node  = inOrder (left node) >> doSomething node >> inOrder (right node)

In Continuation Passing Style:

inOrder :: Node -> m () -> m ()
inOrder Empty cont = cont
inOrder node  cont = inOrder (left node) (doSomething node >> inOrder (right node) cont)

Der Unterschied ist minimal, dennoch ist die zweite Version in 
Continuation Passing Style geschrieben und endrekursiv.

Die Sprache fuer Continuation Passing Style ist uebrigens Scheme, denn 
im Grunde ist das die einzige nicht-esoterische Sprache die echte 
Continuations unterstuetzt.

Wenn du mehr ueber Rekursion lernen moechtest, kann ich dir Scheme sehr 
nahelegen.