Wann besser rekursiv und wann besser iterativ vorgehen?

Hi.

Ich habe mir gerade wieder einmal den Kopf über einen rekursiven Lösungsansatz zerbrochen. Ich wollte meinem Programm klar machen, dass es bei einer Grafik einer Linie folgen und das jeweils letzte Pixel weiß machen soll. Außerdem durfte es nur einer bestimmten Richtung folgen und sich am besten auch noch merken, welche Richtung es noch machen darf (hat es z.B. Südwest erkannt, sollte er auch nur noch west, südwest, oder süd gehen dürfen).

Ich habe es nun halbwegs hinbekommen, aber gemerkt, dass es gar nicht die Lösung meines Problemes darstellt.

Ich bin auf die Lösung gekommen, weil ich nach etlichen Versuchen einfach mal ganz normal, hintereinander weg, programmiert habe um dann irgendwann zu bemerken, dass sich hier etwas wiederholt und das dann rekursiv hinzubiegen.

Und nun möchte ich gern wissen, wie ihr denn solche Lösungen versucht zu entwickeln oder ob ihr mir paar Tipps nennen könnt.

MfG

Etwa so in die Richtung?!:

Snake Contour

Hallo,

Rekursion eignet sich ja meistens dann, wenn man das Ergebnis eines Rekursionsschrittes im nächsten Rekursionsschritt nutzen kann, oder von einem dort benutzten Parameter/Objekt auf das nächste zu verwendende schließen kann.

Ich überlege dann meist, auf welche Weise ich ein solches Ergebnis für den nächsten Schritt nutzen kann. Wenn man sich das klar macht, stösst man dann oft zwangsläufig auf die richtige Rekursion. Dann muss man natürlich noch eine geeignete Abbruchbedingung finden, damit der Stack nicht überläuft.

Das genauer auszuformulieren ist IMHO immer vom jeweiligen Problem abhängig, eine pauschale Aussage ob und in welcher Weise Rekursion verwendet werden kann/sollte lässt sich schwierig treffen.

Gruß, MarsStein

EDIT: oder-Teil im ersten Satz eingefügt.

Hallo Bunnychecker,

Ich habe mir gerade wieder einmal den Kopf über einen rekursiven Lösungsansatz zerbrochen. Ich wollte meinem Programm klar machen, dass es bei einer Grafik einer Linie folgen ...

schon lustig, ungefähr an dieser Stelle dachte ich: "hm, das rekursiv zu machen ist aber nicht so günstig". Es ist also wohl auch ein gutes Stück Erfahrungssache, zu erkennen, ob man etwas rekursiv macht oder nicht. Wie MarsStein sagt, gibt es zwar Anhaltspunkte, aber keinen kleinen, vollständigen Satz an Kriterien.

Rekursion bietet sich fast immer an, wo Bäume im Spiel sind, aber eben nicht nur da. Siehe [Tutorial] Bäume durchlaufen mit Rekursion (und Alternativen).

Jede Rekursion lässt sich in eine Iteration umwandeln und umgekehrt. Siehe Gibt es Rekursionen die sich nicht in eine Iteration umwandeln lassen? Wenn ein Problem wie Türme von Hanoi sich jedoch für Rekursion geradezu anbietet, ist eine iterative Lösung aber oft sehr kryptisch.

herbivore

Ich denke man nutzt immer das, was man am einfachsten implementieren kann. In ganz seltenen Fällen geht es um Dinge wie Performanche: Stack bei Rekursion, evtl. Geschwindigkeit bei einer Lösung.

Rekursion ist grade am Anfang schwerer zu "Durchdenken". Daher würde ich in dem Fall Iterativ anfangen und wenn der Code den Anschein macht zu lang werden, kann man ja doch nochmal rechtzeitig über Rekursion nachdenken.

Das sollte ein natürlich nicht davon abhalten vorher mal nach ähnlichen Problemen zu googeln um vll schon vorher eine Lösung zu finden.

Hi,

meine Erfahrung ist, dass rekursive Methoden in den meisten Fällen einfacher zu lesen und zu schreiben sind. Klar kann es etwas Einarbeitungszeit benötigen, wenn man lange Zeit nur iterativ gearbeitet hat. Wichtig ist, dass du darauf achtest, dass der Stack nicht zu sehr anwächst, wie bereits von MarsStein erwähnt. Leider unterstützt die CLR soweit ich weiss nur auf x64 Tail Call Optimization, ansonsten hätte man damit einen Overflow vollkommen ausschließen können. Aber es ist trotzdem wissenswert, da es in anderen Sprachen/Systemen unterstützt wird und hoffentlich mit Hilfe von F# auch bald in die x86 CLR kommt.

Leider unterstützt die CLR soweit ich weiss nur auf x64 Tail Call Optimization, ansonsten hätte man damit einen Overflow vollkommen ausschließen können

Was meinst du damit ???

[...]x64 Tail Call Optimization [...] Overflow[...]
Was meinst du damit ???

Siehe z.B. The Case of The Failed Demo – StackOverflowException on x64 - B# .NET Blog

Leider unterstützt die CLR soweit ich weiss nur auf x64 Tail Call Optimization, ansonsten hätte man damit einen Overflow vollkommen ausschließen können

Was meinst du damit ???

Hi,

damit Du dir nicht den ganzen Kram aus dem Link durchlesen musst erkläre ich es hier noch einmal kurz.

Jede Rekursion kann in eine äquivalente Tail-Recursive Variante umgeschrieben werden. Das heisst, dass der letzte Ausdruck in der Funktion der Rekursionsaufruf ist.

Bsp:

int Rek(int i) {
  if(i <= 0) {
    return 0;
  }
  return Rek(i-1) + i; //der letzte Auruf in diesem Ausdruck ist die Addition
}

int Rek(int i, int j = 0) {
  if(i <= 0) {
    return i;
  }
  return Rek(i-1, j+i); //der letzte Aufruf ist die Rekursion
}

Im zweiten Fall kann der (JIT-)Compiler optimieren, da nichts auf dem Stack gehalten werden muss. Es werden hier nur die Werte der Parameter geändert und an den Anfang der Methode gesprungen. Somit wird kein Stack aufgebaut und es kann nicht zu einem Overflow kommen.

Ähmm, der erste Fall ist doch Tail-Recursive. Oder muss man das für den MS-Compiler umschreiben? Das sollte er doch erkennen.

int Rek(int i) {
  if(i <= 0) {
    return 0;
  }
  return i + Rek(i-1);
}

Ich hoffe, dass dies der JIT erkennt.

Tail-Recursive beschreibt die Reduzierung der Aufruftiefe. Der Aufruf von Rek sieht wie folgt aus

Rek(10)
10 + Rek(10-1)
10 + 9 + Rek(9-1)
10 + 9 + 8 + Rek(8-1)
...

So, jetzt kann man die Aufruftiefe reduzieren. Man muss lediglich die Operationen ausführen (ob das rechts oder links steht ist egal). Bei Tail-Recursive Unterstützung.

Rek(10)
10 + Rek(10-1)
19 + Rek(9-1)
27 + Rek(8-1)
...

Folgendes solltest du beachten. Ich wusste bis heute nicht, dass .NET tail recursive Unterstützung besitzt. Daher ist der geschilderte Fall mit vorsicht zu genissen. Er beschreibt den allgemeinen Fall, wenn man von tail recursive spricht. Ich kenne es aus Scala.
@Corpsegrinder Er kennt das die .NET-Plattform?

@Siassei:

Ich glaube Du hast Tail-Recursion nicht ganz verstanden. Du machst da einen Fehler, der häufig gemacht wird. Der Ausdruck "return Rek(i-1) + i;" is äquivalent zu "return i + Rek(i-1)". Der letzte Aufruf ist in beiden Fällen die Addition. Daher muss auch in beiden Fällen ein Stack aufgebaut werden, damit diese Addition erfolgreich durchgeführt werden kann. Eine Tail-Recursion darf aber als letzte Anweisung nur den Rekursionsaufruf haben. Also nur "return Rek(i-1)" und da wir trotzdem das Ergebnis berechnet haben wollen, mussen wir es als Parameter mitschleifen. Also die neue Methode mit der Signatur Rek(int, int). Im Normalfall würde man natürlich um eine Manipulation zu verhindern eine Helpermethode schreiben, auf die der Anwender keinen Zugriff hat, also in Falle von C# eine private Methode, im Falle von Scala würde man diesen Helper natürlich innerhalb der eigentlichen Funktion deklarieren.

edit:

Probier einfach mal folgenden Code aus, dann siehst du anhand des Stack Trace, dass die erste Variante keineswegs Tail-Recursive ist:

object Main {

  def main(args: Array[String]) {
    try {
      rec(4)
    } catch {
      case e: Exception => println(e.getStackTraceString)
    }

    try {
      tailrec(4)
    } catch {
      case e: Exception => println(e.getStackTraceString)
    }
  }
  
  def rec(i: Int): Int = if(i <= 0) throw new Exception("Bumm") else rec(i-1) + i;

  def tailrec(i: Int) = {
    def helper(i: Int,j: Int): Int = if(i<=0) throw new Exception("Bumm") else helper(i-1, j+i)
    helper(i,0)
  }
}

edit 2:

Btw. kann man auf mit der @tailrec Annotation testen, ob eine Methode Tail-Recursive ist. 😉