Alle Wörter der Länge n mit 0 und 1

[JblueG]

Hey,

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:

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 =)

 

[Marcinek]

Das ist definitiv nicht rekursiv ;D.

 

[JblueG]

Ok, kannst du mir auch sagen warum?

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?

 

[JCODA]

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?

public class Recursion {
	public static void main(String[] args) {
		printDownToZero(5);
	}
	
	public static void printDownToZero(int n){
		if(n>=0){			
			System.out.println(n);
			printDownToZero(n-1);
		}		
	}

}

Hier wird auch ein gewisser Teil wiederholt, und zwar genau so lange wie n>=0 🙂

 

[JblueG]

Was willst du mir jetzt damit genau sagen?

Denkst du meine Lösung ist rekursiv oder nicht?
Soll deins eine rekursive Lösung sein?

 

[Kevin94]

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:

for(long i=0;i<(1l<<(n+1));i++)
{
    System.out.println(Integer.toBinaryString(i));
}

 

[JCODA]

Was willst du mir jetzt damit genau sagen?

Denkst du meine Lösung ist rekursiv oder nicht?
Soll deins eine rekursive Lösung sein?

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 😛

 

[KuhTee]

Denkst du meine Lösung ist rekursiv oder nicht?

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.

Also man kann jeden rekursiven Algorithmus auch iterativ schreiben, bin mir aber nicht sicher, ob das umgekehrt auch gilt?

[...]rekursiv bedeutet, dass die gleiche Methode mit unterschiedlichen Parametern aufgerufen wird.

Es muss nicht zwingend die gleiche Methode sein. Es können sich durchaus auch zwei oder mehr Methoden wechselseitig aufrufen.

 

[JblueG]

@JCODA:

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?

 

[JblueG]

@KUHTEE

also mein Algorithmus ist NICHT rekursiv obwohl ich ihn iterativ programmiert habe?
Bist du dir sicher?

Ist Iteration nicht einfach nur eine programmiertechnische Möglichkeit rekursive Algorithmen umzusetzen?

 

[KuhTee]

also mein Algorithmus ist NICHT rekursiv obwohl ich ihn iterativ programmiert habe?

Häh? ???:L 😀

Ist Iteration nicht einfach nur eine programmiertechnische Möglichkeit rekursive Algorithmen umzusetzen?

Ä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.

 

[JblueG]

@All

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.

 

[pappawinni]

Rekursion bedeutet gewissermassen, dass ein Algorithmus sich selbst aufruft.

Rekursion:
hauAlleBaeumeUm
Wenn noch ein Baum steht (Abbruchbedingung)
geh zum nächsten Baum und hau ihn um und dann hauAlleBaeumeUm


Iteration:
hauAlleBaeumeUm
Für alle stehenden Bäume
hau den Baum um.

 

[xehpuk]

Endlositeration und -rekursion:

public class ToInfinityAndBeyond {
	void iterative() {
		while (true);
	}
	
	void recursive() {
		recursive();
	}
}

Fakultät iterativ und rekursiv berechnen:

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;
	}
}

 

[KuhTee]

Rekursion:
hauAlleBaeumeUm
Wenn noch ein Baum steht (Abbruchbedingung)
geh zum nächsten Baum und hau ihn um und dann hauAlleBaeumeUm


Iteration:
hauAlleBaeumeUm
Für alle stehenden Bäume
hau den Baum um.

Ich finde nicht, dass das den Unterschied zwischen Iteration und Rekursion sonderlich gut darstellt...

 

[pappawinni]

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.

 

[KuhTee]

Dem Beispiel von xehpuk hätt ich nix hinzuzufügen.

 

[JblueG]

Okay, dankeschön. Ich habs verstanden.