Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
ich soll 2 Algorithmen entwickeln, die jeweils alle Wörter der Länge n ermitteln und ausgeben, die man aus 0-en und 1-en zusammenstellen kann.
Einen rekursiven Algorithmus und einen nicht-rekursiven.
Im Moment sieht meine Lösung so aus:
Java:
public class WoerterMit01 {
public static void main(String[] args) {
int n = 3;
ArrayList<String> alteWoerter = new ArrayList<String>();
for (int zaehler = 0; zaehler < n; zaehler++) {
ArrayList<String> neueWoerter = new ArrayList<String>();
if (alteWoerter.size() == 0) {
alteWoerter.add("0");
alteWoerter.add("1");
} else {
for (String string : alteWoerter) {
neueWoerter.add(string + "0");
neueWoerter.add(string + "1");
}
alteWoerter = neueWoerter;
n++;
}
}
for (String string : alteWoerter) {
System.out.println(string);
}
}
}
Was meint ihr dazu? Das ist doch eine rekursive Lösung oder?
Jede for-Schleife ist doch eigentlich eine rekursive Lösung oder?
Bin mir im Moment so unsicher.
Hat jemand eine Idee wie ich das nicht-rekursiv lösen kann?
Ich kann leider auch gerade nicht sagen, ob die Lösung funktioniert weil mein Eclipse und Netbeans beide spinnen.
Hoffentlich kann mir jemand helfen!
Danke schonmal =)
soweit ich das im Internet nachlesen kann gehört die for-Schleife SEHR WOHL zur primitiven Rekursion.
Deine Antwort wirkt auf mich nicht, als hättest du dir viele Gedanken gemacht.
Ich meine, wenn ich eine for-Schleifen-Lösung und eine rekursive Lösung als Baum aufmalen würde, dann würden die Bäume doch genau gleich aussehen oder?
Meiner Meinung nach KANN man dieses Problem garnicht rekursiv lösen weil man ja nie weiß wie groß n ist und man deswegen einen bestimmten Teil des Programms immer so lange wiederholen muss bis n erreicht ist.
Das heißt doch eine nicht-rekursive Lösug zu machen ist unmöglich oder?
Meiner Meinung nach KANN man dieses Problem garnicht rekursiv lösen weil man ja nie weiß wie groß n ist und man deswegen einen bestimmten Teil des Programms immer so lange wiederholen muss bis n erreicht ist.
Das heißt doch eine nicht-rekursive Lösug zu machen ist unmöglich oder?
Ich glaube du verwechselt hier die Begriffe iterativ und rekursiv und die gepostete Lösung ist rein iterativ. Wenn man ein Array in einer Schleife durchläuft sagt man, das man darüber iteriert, das Interface, das Klassen implementieren müssen, um in einer foreach-Schleife verwendet werden zu können heist deshalb auch Iterable. Rekursiv ist, wenn du innerhalb der Methode die Methode selbst wieder aufrufst. Das was JCoda gepostet hat, ist ein Beispiel was Rekursion ist.
Und jede Schleife kann man afaik auch rekursiv abarbeiten, wenn man mal davon absieht das es einem bei zu vielen durchläufen einen StackOverflowError schmeist.
PS: weil die Aufgabe so schön ist, und du das wahrscheinlich sowieso nicht verwenden kannst:
Ich wollte dir lediglich ein Beispiel geben, dass man sehr wohl Dinge auch rekursiv lösen kann, die eine n-malige Abarbeitung verlangen.
Deine Lösung ist iterativ, rekursiv bedeutet, dass die gleiche Methode mit unterschiedlichen Parametern aufgerufen wird.
@Kevin: na, nich ganz, dein Code compiled gar nicht, und wenn du Long.toBinaryString(int i) verwenden würdest, kommen da alle Möglichkeiten für n+1 und darunter raus
Sie ist es nicht. Man kann natürlich rekursive Algorithmen auch in iterativer Form implementieren (also iterative Programmierung, Algorithmus weiterhin rekursiv), aber das tust du nicht.
Eine recht typische Eigenschaft von Rekursion ist die, dass das Ergebnis erst NACH der Abbruchbedingung "erzeugt" wird. Die Abbruchbedingung der Rekursion stellt sozusagen den Startpunkt der eigentlichen Berechnung dar. Die klassischen Beispiele (z.B. Fibonacci und Fakultät) zeigen das eigentlich recht deutlich.
Und jede Schleife kann man afaik auch rekursiv abarbeiten, wenn man mal davon absieht das es einem bei zu vielen durchläufen einen StackOverflowError schmeist.
achso. Ja was ich meinte war eigentlich, dass man Dinge, die eine n-malige Ausführung verlangen NUR rekursiv lösen kann.
Selbst wenn ich es iterativ programmiere, so ist der Algorithmus an sich doch rekursiv. Das meinte ich eigentlich damit.
Was meinst du dazu?
Äh... nein. Wo ist denn bei dir die Abbruchbedingung? Tipp: "zaehler < n" bricht die SCHLEIFE und damit den kompletten Algorithmus ab, das ist aber was komplett anderes als die Abbruchbedingung in einer Rekursion. Dann folgt in der Rekursion erst der so genannte rekursive Aufstieg. Davon ist bei dir absolut nix zu sehen.
Ich denke es hilft, wenn man sich zuerst einmal über die mathematischen Hintergründe von Rekursion schlau macht.
hmm wenn ich Wikipedia richtig verstehe kann man zwar jede primitive Rekursion durch eine iterative Lösung ersetzen und umgekehrt es ist aber trotzdem nicht das gleiche.
public class ToInfinityAndBeyond {
void iterative() {
while (true);
}
void recursive() {
recursive();
}
}
Fakultät iterativ und rekursiv berechnen:
Java:
public class Factorial {
int iterative(int n) {
int product = 1;
for (; n > 1; n--) {
product *= n;
}
return product;
}
int recursive(int n) {
return n > 1 ? n * recursive(n - 1) : 1;
}
}
Dann erklär das doch mal selbst.
Das einzig relevante für Rekursion ist, dass der Algorithmus durch sich selbst definiert ist.
Keine Ahnung wie du das besser verstehst.
