Willkommen auf myCSharp.de! Anmelden | kostenlos registrieren
 | Suche | FAQ

Hauptmenü
myCSharp.de
» Startseite
» Forum
» Suche
» Regeln
» Wie poste ich richtig?

Mitglieder
» Liste / Suche
» Wer ist online?

Ressourcen
» FAQ
» Artikel
» C#-Snippets
» Jobbörse
» Microsoft Docs

Team
» Kontakt
» Cookies
» Spenden
» Datenschutz
» Impressum

  • »
  • Community
  • |
  • Diskussionsforum
Wann besser rekursiv und wann besser iterativ vorgehen?
Bunnychecker
myCSharp.de - Member



Dabei seit:
Beiträge: 224

Themenstarter:

Wann besser rekursiv und wann besser iterativ vorgehen?

beantworten | zitieren | melden

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
private Nachricht | Beiträge des Benutzers
dr4g0n76
myCSharp.de - Experte

Avatar #avatar-1768.jpg


Dabei seit:
Beiträge: 2.896
Herkunft: Deutschland

beantworten | zitieren | melden

Etwa so in die Richtung?!:

Snake Contour
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dr4g0n76 am .
Seit der Erkenntnis, dass der Mensch eine Nachricht ist, erweist sich seine körperliche Existenzform als überflüssig.
private Nachricht | Beiträge des Benutzers
MarsStein
myCSharp.de - Experte

Avatar #avatar-3191.gif


Dabei seit:
Beiträge: 3.163
Herkunft: Trier -> München

beantworten | zitieren | melden

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.
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von MarsStein am .
Non quia difficilia sunt, non audemus, sed quia non audemus, difficilia sunt! - Seneca
private Nachricht | Beiträge des Benutzers
herbivore
myCSharp.de - Experte

Avatar #avatar-2627.gif


Dabei seit:
Beiträge: 49.486
Herkunft: Berlin

beantworten | zitieren | melden

Hallo Bunnychecker,
Zitat
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
private Nachricht | Beiträge des Benutzers
Tarion
myCSharp.de - Member



Dabei seit:
Beiträge: 381

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 401

beantworten | zitieren | melden

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.
private Nachricht | Beiträge des Benutzers
user8744
myCSharp.de - Member



Dabei seit:
Beiträge: 1.150

beantworten | zitieren | melden

Zitat
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 ???
private Nachricht | Beiträge des Benutzers
dN!3L
myCSharp.de - Experte

Avatar #avatar-2985.png


Dabei seit:
Beiträge: 2.891

beantworten | zitieren | melden

Zitat von Sebastian.Lange
Zitat von Corpsegrinder
[...]x64 Tail Call Optimization [...] Overflow[...]
Was meinst du damit ???
Siehe z.B. The Case of The Failed Demo – StackOverflowException on x64 - B# .NET Blog
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von dN!3L am .
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 401

beantworten | zitieren | melden

Zitat von Sebastian.Lange
Zitat
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.
private Nachricht | Beiträge des Benutzers
Siassei
myCSharp.de - Member



Dabei seit:
Beiträge: 401

beantworten | zitieren | melden

Ä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?
private Nachricht | Beiträge des Benutzers
Corpsegrinder
myCSharp.de - Member



Dabei seit:
Beiträge: 401

beantworten | zitieren | melden

@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. ;-)
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von Corpsegrinder am .
private Nachricht | Beiträge des Benutzers