Array nach Wert prüfen rekrusiv (java)?
Hi sagen wir mal ich habe einen COde der so aussieht:
public static int calculateBinomialCoefficient (int n, int k)
{
if (k == 1)
return n;
else if (n >= k && k == 0)
return 1;
else
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt. EIne Möglichkeit damit das besser läuft ist es berechente Binomialkoeffizienten in einem zwei dimensionalen Array zu speichern und vor einem rekursiven Aufruf zu prüfen, ob die Lösung bereits 1x exisitert hat. EInen Array haben wir schon gegeben, mit der perfekten Länge.Dann habe ich mir das überlegt:
public static int calculateBinomialCoefficient (int n, int k)
{
if (k == 1)
return n;
else if (n >= k && k == 0)
return 1;
else
for (int a=0; a<array.length;a++)
{
for (int b=0; b<array.length;b++)
{
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
}
}
}
}
(Ich hoffe kann man erkennen Tabs sind bisschen verrückt.)
Aber warum funktioniert das nun nicht? Habe doch alles beachtet oder?
3 Antworten
Gemeint ist eine Abbruchbedingung für die Rekursion, du könntest auch einen Zähler (Static) einbauen und auf diese Weise verhindern, das ein Stackoverflow passiert.
Danke dir, aber den Array haben wir schon vorgegeben bekommen, deshalb will der Prof, dass wir das mit einem Array mal versuchen, ist halt auch nur freiwillig deshalb denke ich mal komplex, aber wollte mal nur die richtige Lösung sehen um es nachvollziehen zu können. Weil der gibt uns nie Lösungen hahahahaha
Nun hat mein Prof gemeint, dass die rekursion nicht linear ist und zu vielen gleichen Aufrufen mit gleichen Parameterkombis führt.
Hat dir dein Prof auch erklärt, dass man nach Möglichkeit immer auf Rekursion verzichten sollte, weil sie langsamer, ineffizienter und eine deutlich größere Belastung für den Speicher ist, verglichen mit Iteration?
Darf ich fragen wie alt dein Prof ist? ;-)
Ansonsten macht das hier keinen Sinn:
else{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
if(array[a][b]==0){
array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
}
Das if wird niemals erreicht!
Nachtrag:
Dies wäre meine Lösung, mit entsprechendem Test-Dummy:
import java.util.ArrayList;
import java.util.Random;
public class MyClass
{
public static ArrayList<String> savedresults = new ArrayList<String>();
public static void main(String args[])
{
int n;
int k;
Random wuerfel = new Random();
for (int i=0; i<100; i++)
{
n = 1 + wuerfel.nextInt(6);
k = wuerfel.nextInt(n);
System.out.println(""+n+" über "+k+" = "+checkBinomialCoefficient(n,k));
}
}
public static int checkBinomialCoefficient (int n, int k)
{
if (k>n)
return 0;
else if (k==1)
return n;
else if (k==0 || n==k)
return 1;
else
{
String[] result;
for (int i=0; i<savedresults.size();i++)
{
result = savedresults.get(i).split(" ");
if (n==Integer.parseInt(result[0]) && k==Integer.parseInt(result[1]))
{
System.out.print("Dies lag in unserer Liste: ");
return Integer.parseInt(result[2]);
}
}
int calc;
if (k<(n-k))
calc=calculateBinomialCoefficient (n, k);
else
calc=calculateBinomialCoefficient (n, (n-k));
savedresults.add(n+" "+k+" "+calc);
return calc;
}
}
public static int calculateBinomialCoefficient (int n, int k)
{
if (k>1)
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
else
return n;
}
}
Getestet auf https://www.jdoodle.com/online-java-compiler/
Funktioniert so, aber wie gesagt, ist Rekursion alles andere als sinnvoll!
Naja, zu nächst einmal stellt sich die Frage, ob das hier sinnvoll ist:
if (array[a][b]==(n * calculateBinomialCoefficient(n - 1, k - 1) / k)
{
return array[a][b];
}
Ich dachte der Sinn des Array sollte es sein, dass man die Berechnung nicht noch mal durchführt, stattdessen schickst du n und k den kompletten Weg durch die Rekursion nur um abzufragen, ob der Wert schon mal gespeichert wurde. UND wenn nicht, dann führst du die Berechnung sogar noch mal durch! (im else Zweig).
Der ganze Teil hat absolut NULL Mehrwert, sondern ist schon fast ein Verbrechen!
Zwar könnten wir dir eine funktionierende Lösung vorsagen, aber beim Programmieren muss man sich die Logik selbst erarbeiten. Man kann vieles kopieren und muss das Rad nicht unnötig neu erfinden, aber hierbei geht es ja gerade darum, dass du dir gedanklich durchspielst, was überhaupt mit dem Programm-Code passiert.
Genau, aber bei mir baut sich dei Logik irgendwie auf wenn ich was korrektes sehe. Wollte nur bisschen mein VErständnis aufbauen
Sagen wir einfach mal so. Bei der Array-Abfrage solltest du n und k übergeben und damit gucken, ob die Werte schon mal durchgerechnet wurden.
Wenn ja, soll er die Array Werte einfach ausspucken und die Rekursion abbrechen und nur im Falle, dass es die Berechnung noch nicht gab, solltest du die Berechnung durchführen.
Aber Achtung, du wirst hier zwangsläufig in den Konflikt kommen, dass n und k sich mit jedem Aufruf verkleinern und demnach nicht mehr das Originale n und k darstellen.
Entsprechend wäre die Array-Abfrage innerhalb der Funktion wenig hilfreich. Man würde das Auslagern und nur im benötigten Fall die Rekursion aufrufen.
Sorry würde mir echt helfen das in code zu sehen hahahaha, habe es gerade versucht aber naja.
Du willst den Wert einer Berechnung in einem zweidimensionales Array speichern. Ob das jetzt sinnvoll ist oder nicht, sei mal dahingestellt, aber dann sollte deine Abfrage doch eigentlich so sein, dass man fragt ob es bereits ein Array[a] mit dem Wert n gibt und ein Array[a][b] mit den Werten n und k.
Und nicht vergleicht, ob der Wert mit array[a][b] mit dem Ergebnis der Rekursion übereinstimmt. Denn wozu das Ergebnis speichern, wenn man es ohnehin neu berechnet.
Alles in allem wirst du dann aber eine weitere Schleifenform benötigen, die das Array durchläuft. Zwar könntest du ein entsprechend großes Array vordefinieren (also mit n und k), aber dafür brauchst du auch eine Schleife und verschwendest Speicherplatz. Auch sortieren wäre eine Möglichkeit, aber für mich ist es in etwa so, als ob man die Schleife nur durch eine andere ersetzt.
Wie sinnvoll das ist, bleibt im Raum stehen. Wenn es keine Hausaufgabe ist, würde ich das fallen lassen. Ansonsten müsstest du den Teil des Abfragens und Abspeicherns komplett auslagern usw.
Mein Ansatz ginge in die folgende Richtung, wobei ich eine ArrayList nutze, mit string split arbeite etc. Die ArrayList müsste aber auf Klassenebene definiert werden, also so, dass du von überall aus Zugriff darauf hast.
public static int checkBinomialCoefficient (int n, int k)
{
int a;
String[] result;
String tmp=""+n+""+k+"";
if (k==1)
return n;
else if (n >= k && k ==0)
return 1;
else
{
for (a=0; a<arraylist.size();a++)
{
result = s.split(" ");
if (result[0]==tmp)
{
return Integer.parseInt(result[1])
}
}
int calc = calculateBinomialCoefficient (int n, int k);
arraylist.add(tmp+" "+calc);
return calc;
}
}
public static int calculateBinomialCoefficient (int n, int k)
{
return (n * calculateBinomialCoefficient(n - 1, k - 1) / k);
}
Und du würdest nicht mehr calculateBinomialCoefficient aus dem Programm aufrufen, sondern checkBinomialCoefficient
Auch habe ich es nicht getestet, Fehler sind also denkbar.
Aber wie gesagt, wenn du dir sowas nicht selbst logisch erarbeiten kannst, wie willst du jemals programmieren lernen? Programmieren kann man nicht auswendig lernen, man muss es sich logisch selbst erarbeiten. Quasi wie Mathematik.
Auch habe ich deine eigentliche Rekursion nicht verbessert. Du hast unnötig viele Aufrufe, denn du benötigst lediglich k Aufrufe, beziehungsweise (n-k) Aufrufe, je nach dem was kleiner ist.
Um das zu verstehen, solltest du den Binomialkoeffizient mal von Hand berechnen. Nehmen wir mal 6 über 3:
6! / (3! * (6-3)!
= 6 * 5 * 4 * 3 * 2 * 1 / (3 * 2 * 1 * 3 * 2 * 1)
= 6 * 5 * 4 / 3 * 2 * 1
Jetzt solltest du dir ein Konzept erarbeiten, wie du das mittels Rekursion umsetzen kannst. Aber grundsätzlich: Kein Programmierer, nicht ein einziger, würde auf die Idee kommen, sowas als Rekursion zu berechnen!!! Deswegen stellte ich die Frage nach dem Alter des Profs. ;-)
Ich habe meine Antwort um meine persönliche Lösung ergänzt, da ich gerade etwas Langeweile hatte.
Normalerweise übernehme ich keine Hausaufgaben, sondern gebe nur Hilfestellungen. Auch denke ich, dass dir diese Lösung kein Stück weiterhilft, da du sie dir nicht selbst erarbeitet hast. Auswendiglernen hilft beim Programmieren nicht!
"weil sie langsamer, ineffizienter und eine deutlich größere Belastung für den Speicher ist"
Nicht immer. Endrekursion kann so schnell sein wie iteration wenn der compiler tail call optimization hat.
Es gibt Situationen wo Rekursion sich zur Iteration nur geringfügig negativ bemerkbar macht, aber die Speicherbelastung ist in jedem Fall größer, so bald die Funktion mehr als einmal sich selbst aufruft und man muss es anders betrachten:
Es gibt KEINEN Fall, wo Rekursion effizienter wäre. Sie sieht für den Programmierer schöner aus und streichelt so ein bisschen unser Ego, weil es ein schönes Gedankenspiel sein kann und in nicht mal wenigen Fällen erspart sie uns einiges an Programmierarbeit, aber die Code-Ästhetik steht weit hinter Performance!
"aber die Speicherbelastung ist in jedem Fall größer, so bald die Funktion mehr als einmal sich selbst aufruft"
Nein, bei Endrekursion eben nicht.
Nein, bei Endrekursion eben nicht.
Der Speicherplatz kann dabei wiederverwertet werden, trotzdem muss mit dem Werten im Speicher erst mal die Funktion neu aufgerufen werden. Es wird also trotzdem noch geringfügig mehr Speicher belastet, als auch ausgelastet.
Zumindest meines Wissens nach, aber da ich auf Rekursion praktisch IMMER verzichte, muss ich zugeben, dass ich mich nie tiefgründiger mit dem Thema beschäftigt habe.
Nun, es gibt Programmiersprachen wie Haskell die keine iteration haben, da wird dir das schwer fallen auf Rekursion zu verzichten.
Bei eine Endrekursion können die werte von der vorherigen iteration verworfen werden, der Speicherplatz ist also gleichbleibend egal wie oft die Funktion sich selbst aufruft.
Wenn es keine Endrekursion ist(oder einfach keine tail call optimization stattfindet) wird für jeden Funktionsaufruf zusätzlicher Speicher benötigt.
Nun, es gibt Programmiersprachen wie Haskell die keine iteration haben, da wird dir das schwer fallen auf Rekursion zu verzichten.
Nun, es gibt auch Leute die noch mit einem Rechenschieber arbeiten. Wem es gefällt soll es tun, aber deswegen würde ich das trotzdem nicht mehr in der Schule unterrichten. Höchstens mal mit einfachen Beispielen erklären, wie ein Rechenschieber funktioniert.
Bei eine Endrekursion können die werte von der vorherigen iteration verworfen werden, der Speicherplatz ist also gleichbleibend egal wie oft die Funktion sich selbst aufruft.
Die Variablen werden erst nach dem erneuten Funktionsaufruf "frei", entsprechend benötigt man für den Funktionsaufruf temporär extra Speicherplatz. Dies ist zwar nur geringfügig, trotzdem vorhanden.
Und es gilt immer noch die selbe Aussage: Rekursion hat außerhalb der Code-Ästhetik keinen einzigen Vorteil, nur Nachteile! Damit erübrigt sich jede weitere Diskussion, oder? ;-)
Noch als Nachtrag:
Ist erst einmal eine endrekursive Lösung gefunden worden, so ist es meistens leicht, daraus eine iterative Lösung zu entwickeln, die hinsichtlich der Laufzeit immer die bessere Variante darstellt.
http://www.lab4inf.fh-muenster.de/lab4inf/docs/Informatik-I/Informatik_I_07_Erweiterte_Rekursion.pdf
Nun, also wir haben in einem modul an der hochschule mit Haskell gearbeitet.
Aber klar, benutzt kaum noch wer, ist 2021 auf 0% Beliebtheit gefallen, lol https://pypl.github.io/PYPL.html
"Die Variablen werden erst nach dem erneuten Funktionsaufruf "frei", entsprechend benötigt man für den Funktionsaufruf temporär extra Speicherplatz."
Nein. Sie werden davor frei... Der Speicherplatzverbrauch ist Identisch. Wenn du dich nicht damit beschäftigt hast, warum behauptest du einfach irgendwas?
In dem Dokument wird nicht von tail call optimization ausgegangen.
Ich sagte, ich habe mich nie ausgiebig damit beschäftigt. Was ich behaupte war mein Wissensstand, den ich irgendwo mal gelesen habe. Dass der Speicherplatzverbrauch zwar nicht übermäßig ist, aber immer noch mehr als bei einer Iteration, da die Variablen erst nach dem eigentlich Aufruf frei werden.
Und selbst wenn das nicht der Fall sein sollte und beide Varianten gleich viel Speicherplatz als auch Speicherzugriffe benötigen (was ich stark bezweifle nach allem was ich über das Thema weiß), steht es doch außer Frage, dass es hinsichtlich der Laufzeit sehr viel schlechter ist.
In anderen Worten:
Wann Rekursion? Never!
Das zweite ergibt so keinen sinn.
Eine if verzweigung nach einem return wird nie erreicht.
Okay, könntest Du mir vielleicht sagen wie es richtig aussehen würde? Ist auch keine Hausaufgabe oder so, will nur mein Verständnis verbessern, bei mir ist es so, dass nachdem ich einen Code richtig gesehen habe, ich erst Verständnis aufbaue und es beim nächsten Mal kann
Und wie wäre es korrekt? Naja keine Ahnung. Die Rekursion war eine Hausaufgabe das zweite ist "freiwillig", will nur mein Verständnis verbessern, bei mir ist es so, dass nachdem ich einen Code richtig gesehen habe, ich erst Verständnis aufbaue und es beim nächsten Mal kann. Wi emüsste ich das umändern, dass es korrekt ist