Programm vorwärts statt rückwärts zählen lassen?
Wie mache ich das hier , ohne dabei neue Variablen zu definieren, oder den Input zu verändern, also die Signatur, nur die Methode countBackwards soll verändert werden.
(Java)
Was haltet ihr von dieser Lösung? Ist nicht die beste, aber es funktioniert
3 Antworten
Wer benutzt denn heutzutage bitte noch Rekursion? Altmodisch und unperformant!
Aber okay, wobei ich dann die ganze Methode entsprechend anpassen würde, so dass sie einfach Von x nach y zählt. Wenn x>y zählt sie runter und wenn x<y zählt sie eben hoch:
public class Main {
public static void main(String[] args) {
countFromTo(30,0);
countFromTo(5,15);
countFromTo(-2,-8);
}
public static void countFromTo (int from, int to) {
System.out.print(from + " ");
if (from > to)
from--;
else if (from < to)
from++;
else {
System.out.print("\n");
return;
}
countFromTo(from,to);
}
}
Es ist altbacken aus der Großväterchen-Generation und auf Grund der schlechten Performance schon fast verpönt.
bei rekursion geht es eher darum einen schritt in sich wiederholende einzelteile zu zerlegen
Und bei Iteration?! :)
Je nach Anwendungsgebiet kann Iteration mehr Schreibkram bedeuten - daher fühlen sich manche Entwickler toll, wenn sie ein Codesnippet in 3 Zeilen gedrückt bekommen, wofür man mit Iteration ggf. 10 Zeilen bräuchte - aber da den Code in der Regel keiner sieht und der Computer kein Ego hat, welches es jucken könnte, sollte man Performance immer die oberste Priorität einräumen.
klar ist das konzept alt aber tatsächlich ist rekursion noch heutzutage sehr beliebt je nach datenstruktur und paradigma
in der funktionalen programmierung ist rekursion noch immer sehr beliebt und beim implementieren von datenstrukturen wie bäumen, weil diese von natur aus rekursiv sind
außerdem sehen entwickler den code und wenn performance wirklich so wichtig wäre sollten wir alle am besten anfangen (hochoptimierten) assembler zu schreiben
klar ist das konzept alt aber tatsächlich ist rekursion noch heutzutage sehr beliebt je nach datenstruktur und paradigma
Ich sagte auch nicht unbeliebt. Ich sagte altmodisch und unperformant.
wenn performance wirklich so wichtig wäre
Stimmt, warum sollte wir auf die Idee kommen O(n²) möglichst zu vermeiden, wenn die Performance so unwichtig ist? :)
Ich hatte mal einen Sudoku-Löser mittels Rekursion realisiert, bis ich dann bei 2/3 aller Sudokus eine StackOverflowException bekam...
Von da an nie wieder Rekursion benutzt!
ja aber, altmodisch kann auch beinhalten, dass niemand das nutzt/nutzen sollte
klar sollte man ineffizienz vermeiden, aber performance ist immer noch nicht die oberste priorität und sollte es auch nicht sein
Und das ironische bei der iterativen Lösung war nicht nur, dass diese jedes Sudoku ohne zu Murren gelöst hat, es hat auch die, die die Rekursion lösen konnte wesentlich schneller gelöst.
eyo ich hab mich nicht für die rekursive lösung ausgesprochen (die in meinen augen absolut scheiße ist) sondern für die relevanz von rekursion
aber performance ist immer noch nicht die oberste priorität und sollte es auch nicht sein
Die Priorität der Performance liegt aber weit über der vom Codekonstrukt.
Nochmals: Dem Computer ist die Reihenfolge der Nullen und Einsen egal, daher sollte der Entwickler sein Ego hinten dranstellen und zu einer Lösung greifen, die eventuell weniger schön aussieht oder lästig wirkt, dafür aber eine deutlich bessere Performance abliefert.
Das gilt für alle Bereiche! Auch wenn ich natürlich verstehen kann, dass z. B. bei einer Verzeichnisstruktur es einen in den Fingern juckt, zu Rekursion zu greifen.
da kann ich absolut nicht zustimmen, der computer soll uns helfen und nicht wir dem computer
programmiersprachen sind (größtenteils) für menschen
lesbarkeit, erweiterbarkeit und instandhaltung von code ist wesentlich wichtiger
es geht hierbei nicht um das ego, es geht darum menschen zu helfen
da kann ich absolut nicht zustimmen, der computer soll uns helfen und nicht wir dem computer
Der Computer soll dem Nutzer helfen, nicht dem Programmierer. Und das tut er dann ja auch, wenn er schneller zum gewünschten Ergebnis kommt! :)
ja, programme sind für endnutzer und für endnutzer ist der code egal aber das bedeutet nicht, dass der code für den programmierer egal ist, bzw. der zustand des projekts für den endnutzer
die punkte die ich vorher erwähnt habe wie erweiterbarkeit vom code sind nicht irrelevant für die weiterentwicklung eines programms
außerdem, wenn du jz deinen code wirklich so hart auf performance trimmst, sogar mikrooptimierung betreibst ist es wesentlich wahrscheinlicher, dass du ein unperformanteres produkt rausbekommst oder dass die kosten vom aufwand den ertrag übersteigen, weil du einfach scheiß code geschrieben hast. das ist eine universelle weisheit im programmieren
wäre performance wirklich das oberste gebot beim programmieren, gilt immernoch: wir sollten anfangen mit assembly zu programmieren und jede abstraktionsschicht beim arbeiten mit dem computer niederreißen
die punkte die ich vorher erwähnt habe wie erweiterbarkeit vom code sind nicht irrelevant für die weiterentwicklung eines programms
Natürlich sind sie nicht irrelevant, aber wieso sollte eine iterative statt rekursive Lösung dafür sorgen, dass ein Programm nicht weiterzuentwickeln wäre?
Und ich sage mal, dass jeder Programmierer, der in der Lage ist eine rekursive Lösung zu schreiben, dies auch iterativ hinbekommt.
oder dass die kosten vom aufwand den ertrag übersteigen
Wenn auf Grund einer iterativen Lösung die Kosten den Aufwand übersteigen, dies bei einer rekursiven Lösung aber nicht der Fall ist, würde ich den Entwickler feuern und mir Qualität ins Haus holen.
wäre performance wirklich das oberste gebot beim programmieren, gilt immernoch: wir sollten anfangen mit assembly zu programmieren und jede abstraktionsschicht beim arbeiten mit dem computer niederreißen
Dafür gibt es die Compiler, die es in Maschinencode umwandeln. Das bedeutet aber nicht, dass wir beim Programmieren schlampig arbeiten sollten, nur weil es sich schöner ließt oder einfacher erscheint.
meine punkte waren jz nicht auf iteratives programmieren bezogen sondern auf das konzentrieren auf performance
und was du sagst entspricht nicht dem gebot der obersten performance
compiler haben heutzutage eine sehr gute qualität beim generieren von maschinencode, theoretisch aber bietet dir assembly mehr kontrolle beim optimieren
dementsprechen behaupte ich, dass mit assembly zu programmieren in der theorie dir immer die höchste performance bietet
dementsprechen behaupte ich, dass mit assembly zu programmieren in der theorie dir immer die höchste performance bietet
Dein Argument lautet also, weil man ohnehin schon nicht die optimalste Lösung hat, kann man ruhig noch weitere Performance-Einbußen hinnehmen, wenn es sich dadurch ausschließlich für den Programmierer besser liest?
Sorry, finde ich ein ganz ganz schwaches Argument!!! :)
?
ich habe das nicht gesagt und du gehst auch nicht wirklich auf meine aussage ein
meine aussage ist: performance ist nicht das relevanteste, weshalb wir dementsprechend höhere programmiersprachen benutzen und nicht assembly
und da wir höhere programmiersprachen benutzen und nicht assembly, ist das einbußen von performance offensichtlich ok, wenn es dem programmierer hilft
zudem tendieren compiler dazu den code besser zu optimieren als wenn man assembly per hand geschrieben hätte, auch wenn man potenziell bessere performance mit handgeschriebenem assembly hat
in diesem fall geht das vereinfachen des lebens des programmierers offensichtlich auch mit performance hand in hand
ich schließe performance bei gutem code nicht aus und ich will dir ja nix in den mund legen, aber für mich hört es sich an als ob du guten code für performance ausschließen würdest
außerdem, eingehend auf deinen kommentar: ich finde das argument hast du negativ konnotiert, hört sich aber ziemlich vernünftig an
wenn der code eh kompletter müll ist, wieso nicht simplifizieren und darauf nh basis aufbauen für besseren code?
ich habe das nicht gesagt und du gehst auch nicht wirklich auf meine aussage ein
Doch, hast du. Du sagtest, auf die Performance zu achten wäre nebensächlich und kamst mit dem Beispiel, dass wir ja bereits Performance droppen, weil wir nicht in Assembler programmieren.
Ansonsten beziehe ich alles auf den Kontext, den ich geschrieben habe. Denn alles andere bläht die Unterhaltung zu einem Maß auf, das unnütz ist.
und da wir höhere programmiersprachen benutzen und nicht assembly, ist das einbußen von performance offensichtlich ok, wenn es dem programmierer hilft
Die meisten Programme wären für die absolut meisten Programmierer in Assembler gar nicht zu bewerkstelligen.
Es besteht aber ein riesen Unterschied, ob man geringfügige Performance Einbußen für die Machbarkeit in Kauf nimmt, oder ob man rein aus Bequemlich- und Lesbarkeit erhebliche Performance Einbußen akzeptiert, obwohl man es mit wenig Zeitaufwand besser machen könnte!
Manche Sachen lassen sich auch gar nicht effektiv mit Rekursion realisieren. Siehe den Sudoku-Löser mit der regelmäßigen StackOverflowException.
als ob du guten code für performance ausschließen würdest
Nein, wir definieren guten Code nur scheinbar anders. Während für mich guter Code zur Laufzeit sichtbar wird, ist er für dich im Editor sichtbar. Das eine schließt das andere aber leider viel zu oft aus, daher liegt mein Fokus auf der Laufzeit.
darauf nh basis aufbauen für besseren code?
Besserer Code verzichtet auf Rekursion! Genau das war es, was ich zum Ausdruck bringen wollte! :)
Aber da es dir scheinbar so unendlich wichtig ist:
Es gibt Anwendungsbeispiele, wo ich Rekursion als zulässig erachten würde. Trotzdem sollte man IMMER darauf verzichten, so lange der Weg über die Iteration keinen erheblichen Mehraufwand bedeutet.
Und das ist bei den höheren Programmiersprachen, wie zum Beispiel C#, fast nie der Fall!
Wer benutzt denn heutzutage bitte noch Rekursion? Altmodisch und unperformant!
Blödsinn. Es ist nur für den User Case der Frage nicht sinnvoll.
Blödsinn. Es ist nur für den User Case der Frage nicht sinnvoll.
Und wer bist du, dass du dir ein Urteil darüber erlauben kannst, ob es Blödsinn ist oder nicht?
Es ist ein Fakt, dass die Laufzeit von Rekursion i.d.R. länger ist - was Iteration automatisch performanter macht - und sie ist auch altmodisch, da es früher bei einigen Programmiersprachen keine Iteration gab meines Wissens nach.
Es gibt nur sehr sehr wenige praktische Anwendungsbeispiele, wo Rekursion heutzutage seine Berechtigung hat, zumindest bei höheren Programmiersprachen und selbst da gibt es nichts, was man nicht auch iterativ bewerkstelligen könnte.
Aber natürlich lasse ich mich gerne eines besseren belehren, wenn du mir ein praktisches Beispiel zeigst, wo die Rekursion performanter ist bzw. eine iterative Lösung kaum zu realisieren -> in einer höheren Programmiersprache natürlich wie z. B. Java, C#, etc. :)
Und wer bist du, dass du dir ein Urteil darüber erlauben kannst, ob es Blödsinn ist oder nicht?
Ich arbeite als Software Engineer.
Es ist ein Fakt, dass die Laufzeit von Rekursion i.d.R. länger ist
Das ist kein Problem. Performanz ist dann wichtig, wenn die Anwendung spürbar langsam ist. Zu frühe Optimierung ist die Wurzel allen Übels.
Es gibt nur sehr sehr wenige praktische Anwendungsbeispiele, wo Rekursion heutzutage seine Berechtigung hat, zumindest bei höheren Programmiersprachen und selbst da gibt es nichts, was man nicht auch iterativ bewerkstelligen könnte.
Ich nutze es teilweise. Rekursion bietet manchmal viel einfachere Lösungen als es iterativ zu implementieren.
Das ist kein Problem... Zu frühe Optimierung ist die Wurzel allen Übels.
Warum laufend nachbessern, wenn man es direkt richtig machen kann? Nur Amateure rechtfertigen schlechten Code, weil sie zu faul waren! Und Performance Nachteile als normal darzustellen...
Ich arbeite als Software Engineer.
Ich habe schon einige IT Projekte geleitet - ein Entwickler mit der Einstellung hätte bei mir keinen leichten Stand gehabt!
Rekursion bietet manchmal viel einfachere Lösungen als es iterativ zu implementieren.
Bestreitet auch keiner, aber Code Ästhetik spielt eine untergeordnete Rolle!
Nochmal: Wenn die Anwendung ihre Aufgabe gut erledigt, muss nicht optimiert werden. Ich orientiere mich bei der Entwicklung von Software sehr an der Unix-Philosophie:
Regel 1: Man kann nicht sagen, welcher Programmteil den Hauptteil der Leistung fressen wird. Da Engpässe oft an überraschenden Stellen auftauchen, soll man nichts zur Erhöhung der Geschwindigkeit einbauen, bevor man gezeigt hat, wo der Engpass sitzt.
Regel 2: Miss die Programmlaufzeit. Feile erst an der Geschwindigkeit, wenn du sie gemessen hast und selbst dann erst, wenn der betrachtete Teil einen dominierenden Anteil der Rechenzeit frisst. [Wikipedia]
Und natürlich am KISS-Prinzip:
Das KISS-Prinzip (englisch Keep it simple, stupid) fordert, zu einem Problem eine möglichst einfache Lösung anzustreben. In seiner Grundaussage ähnelt das KISS-Prinzip stark der Aussage von Ockhams Rasiermesser: Wenn es mehrere Erklärungen für einen bestimmten Sachverhalt gibt, dann ist diejenige Erklärung zu bevorzugen, die am einfachsten ist, also mit den wenigsten Annahmen und Variablen auskommt. Es handelt sich hierbei auch um ein Prinzip von Clean Code. [Wikipedia]
Mir gehen die ganzen Software Entwickler, die ohne ihre fancy Frameworks kein Hello World auf den Bildschirm kriegen, auf den Zeiger. Und von denen gibt es leider zu viele.
Ich finde aber keine Philosophie die einem nahelegt:
Schreibe schlechten Code, damit du später was zu optimieren hast.
Zumal doch allgemein bekannt ist, wo in der Regel Performance-Probleme auftreten: unter anderem bei Rekursion!
Und die Laufzeit-Nachteile zeigen sich auch schnell bei nur kleinen Schleifen mit geringer Laufzeit, denn in der Regel gibt es mehrere davon in einem Programm und viele kleine Performance-Nachteile führen dann in der Summe oft zu einem langsamen Programm, ohne dass man einen Übeltäter genau benennen kann.
Ich hatte vor Jahren mal einen Sudoku-Löser geschrieben, einfach auch Spaß an der Freude. Ich dachte mir damals, Rekursion bietet sich ja förmlich an für die Aufgabe und erspart mir einiges an Code. Die Freude war schnell verflogen, als er die Hälfte der schweren Sudokus nicht lösen konnte, weil ich eine StackOverflowException bekam.
Danach noch iterativ geschrieben und nach ein bisschen Denkarbeit war der Code nur geringfügig länger/breiter, aber deutlich schneller, selbst bei den leichten Sudokus.
Seit dem ist meine Wertschätzung für Rekursion gänzlich vergangen. Sie sieht nur schön aus, davon merkt der Nutzer aber nichts - sie hat also keinen Mehrwert, aber viele Nachteile!
Hier ein Beispiel wieso:
public class LangsamerGauss_Iterativ {
public static void main(String[] args) {
long n = 1000000000L;
long st=java.lang.System.currentTimeMillis();
System.out.println("Die Summe von 1 bis " + n + ": " + DerLangsameGauss(n));
long et=java.lang.System.currentTimeMillis();
System.out.println("\nBerechnungszeit: "+(et-st)+" ms");
}
public static long DerLangsameGauss(long x) {
if (x < 0)
return 0;
for (long i = x-1; i > 0; i--) {
x += i;
}
return x;
}
}
Liefert mir das Ergebnis nach 719 ms
public class LangsamerGauss_Rekursiv {
public static void main(String[] args) {
long n = 1000000000L;
long st=java.lang.System.currentTimeMillis();
System.out.println("Die Summe von 1 bis " + n + ": " + DerLangsameGauss(n));
long et=java.lang.System.currentTimeMillis();
System.out.println("\nBerechnungszeit: "+(et-st)+" ms");
}
public static long DerLangsameGauss(long x) {
if (x < 1)
return 0;
else if (x == 0)
return x;
else
return x+DerLangsameGauss(x-1);
}
}
Liefert mir gar kein Ergebnis, da ab einem n von 5855 der Stack überlaufen ist...
Mir ist der Sinn der Aufgabe noch nicht ganz klar.
Was du da hast, ist ein Rückwärtszählen mit einer Manipulation der existierenden Variable und einer Rekursion.
Jetzt könnte es darum gehen, die Variable nicht aktiv zu manipulieren (fou--) oder aber, was ich eher denke, der Rekursion zu entkommen.
Java übergibt, wie C/C++ auch, Kopien des Wertes, sodass du an fou innerhalb der Funktion countbackwards ändern kannst, was du willst, ohne dass main etwas davon mitbekommt. Warum soll man also hier was dran ändern wollen?
Aber falls doch, ersetze
fou--;
countbackwards(fou);
einfach durch
countbackwards(fou-1);
Wo man was dran ändern wollen könnte, ist der rekursive Aufruf, denn der ist enorme Ressourcenverschwendung, da jedes mal ein Wert mehr im Stack, als im Speicher, landet, bis sich die rekursiv aufgerufenen Funktionen nacheinander nach Abarbeitung ihrer Aufgabe beenden. Das mag zwar heute alles viel harmloser sein, als damals, als 640kB noch genug für jeden waren, aber es ist trotzdem schlechter Stil, zumindest dann, wenn es so unnötig ist, wie hier. Manche Sachen kann man halt nur rekursiv machen, aber das geht auch als Schleife.
So und bei Schleife und Zählen denkt man ja gerne an einer for-Schleife. Jetzt sagt aber deine Aufgabenstellung "keine neue Variable", und was ist der Zähler einer for-Schleife? Eine neue Variable.
Dein Freund ist die while-Schleife. Die könnte dann so aussehen:
while (fou>=0) {
System.out.println(fou + " ");
fou--;
}
fou darfst du ja bedenkenlos ändern, wie es ja im ursprünglichen Beispiel schon getan wird. Es ist ja nur eine Kopie des übergebenen Wertes.
Dein alternativer Ansatz ist eine Verschlimmbesserung des ursprünglichen Beispiels. Denn das setzt voraus, dass der übergebene Wert fou immer 30 bleiben wird. Wenn du aber im Hauptprogramm jetzt 40 einträgst oder eine Abfrage "Bitte Zahl eingeben" einbaust, funktioniert es nicht mehr.
Ach ja und zum Thema "keine weitere Variable":
- Ohne Variable kann man nicht zählen. Zumindest also fou als Kopie des übergebenen Wertes geht es nicht.
- Mit einer While-Schleife kommt keine weitere Variable dazu, da die Kopie des übergebenen Wertes fou manipuliert wird.
- Mit einer For-Schleife kommt eine weitere, nämlich der Zähler, immer wieder gerne i genannt (aber wie mein Prof damals meinte, "da könnte auch 'Hugo' stehen")
- Mit der Rekursion erzeugst du im Prinzip 30 neue Variablen, da mit jedem Aufruf eine neue Kopie im Stack abgelegt wird.
also danke für die Anwort, ich möchte jedoch jetzt aus diesem rückwärtszählen eine art vorwärtszählen mache, indem ich bei 0 oder 1 beginne und dann bis zur Zahl hier 30 zähle. Und dann möglichst simpel, indem ich irgendwie was in der methode ändere jedoch nicht an der signatur
Mit Schleife ginge es so:
public static void countBackwards(int fou) {
for(int i = 0; i < fou; i++) {
System.out.println(i+ " ");
}
}
Bis zu welchem Wert soll sie denn zählen? zu dem, den man übergibt, oder?
bis zum übergebenen, also hier bis zur 30, bei meiner lösung müsste man halt immer den Wert verändern (siehe Ergänzung)
Und du darfst sicher keine Schleife verwenden, nur Rekursion?
ja also mache das aus Übung, und wollte halt gucken ob es da irgendwie so ne "mathematische Lösung" gibt, damit das auch für alle zahlen klappt und ich nur den input bei der main ändern muss, bei mir muss ich ja das bei if (61) und bei else die 30 verändern
danke für die schleife, aber nur mit rekursion? also dass ich nur die methode innerhalb veränder und keine neuen variablen hinzufüge und die signatur nicht verändere
hmm ok juut trotzdem danke, (frankabagnale)
"und die signatur nicht verändere"
Aber dann dem Typen den Stern geben, der die Signatur verändert...
bruh.. xD
Ah shit, wie kann ich das rückgängig machen, du hast den Steen verdient
Beim nächsten mal diggi Antworte auf irgendeine Frage und ich gönn dir
also altmodisch würde ich das jz nicht unbedingt nennen und auf die performance kommt es meistens nicht mal unbedingt an
bei rekursion geht es eher darum einen schritt in sich wiederholende einzelteile zu zerlegen