# Rekursiv Vokale zählen



## tanjaHS (11. Apr 2009)

Hallo Leute, 

ich muss in den Übungsaufgaben Vokalen zählen, das ganze aber rekursiv. Dazu habe ich folgendes programmiert. Was aber mir ein OutOfBound Exception liefert, wieso weiss ich nicht ? Könnt ihr bitte mir helfen ?



```
public static int zaehleVokale(String derString, int l, int vokale) {
		
		if(l == 0)
			return 0;
		else if( l == 1 && derString == "a" || derString == "e "
			|| derString == "i" || derString == "o" || derString == "u")
			return 1;
		else if(l > 1)
			if(derString.charAt(l) == 'a'|| derString.charAt(l) == 'e' || derString.charAt(l) == 'i'
				|| derString.charAt(l) == 'o' || derString.charAt(l) == 'u')
			zaehleVokale(derString, l-1, vokale+1);
			else
				zaehleVokale(derString, l-1, vokale);
			
		return vokale;
		
	}
	
	
	public static void main(String[] args) {

		int vokale = 0;
		String derString = "Rettungsdienst";
		int laenge = derString.length();
		println(zaehleVokale(derString, laenge, vokale));

	}
```


----------



## faetzminator (11. Apr 2009)

Du bist wohl C Programmierer, was?
Ein paar Verbesserungsvorschläge:
1. warum übergibst du von main() die Länge des Strings?
2. bei l == 1 nicht mit == Strings vergleichen, sondern mit .equals()
3. ein Array von der Länge l besitzt die Indexes 0 - (l-1), du versuchst aber auf l zuzugreifen.
4. Mach doch eine 2. Methode, welche das 0 der Vokale übergibt
5. Rekursion ist meist relativ unschön.
Das sollte für den Anfang reichen


----------



## 0x7F800000 (11. Apr 2009)

faetzminator hat gesagt.:


> 5. Rekursion ist meist relativ unschön


tüürkishce gitaarre kannsu nich schepielen, wo kommsu denn heer?! ;(


----------



## faetzminator (11. Apr 2009)

Abgesehen davon, dass dies eine relativ relative Aussage war, bin ich ein Schweizer


----------



## 23 (11. Apr 2009)

Rekursion ist absoult toll!!

Auf die schnelle:


```
public static void vokRek(String x, int i) {
		
		if(i >= x.length())
			return;
		
		if(x.charAt(i) == 'a' || x.charAt(i) == 'e' || x.charAt(i) == 'i' ||
				x.charAt(i) == 'o' || x.charAt(i) == 'u') {
			
			System.out.print(x.charAt(i));
			
		}
		
		vokRek(x, ++i);
		
	}
```

Aufruf: vokRek("hallo wie gehts?u",0);


----------



## 23 (11. Apr 2009)

Ein String ist in Java ein CharArray!


----------



## Marco13 (11. Apr 2009)

_1. warum übergibst du von main() die Länge des Strings?_
Weil des String von hinten durchsucht werden soll - das l ist der Index, an dem der Vokal-check gemacht wird. Das ist auch der Grund für die Exception. Bei l=2 wird auf index 2 zugegriffen, obwohl es nur bis index l-1 geht, wie du auch schon unter 3. gesagt hast.

_2. bei l == 1 nicht mit == Strings vergleichen, sondern mit .equals()_
Wobei man auch dort charAt(0) verwenden könnte.

_5. Rekursion ist meist relativ unschön._

Aber manche Aufgaben sind nur damit elegant lösbar (z.B. Backtracking et al).

Es fehlen aber noch "return"s im (l > 1)-Fall...


----------



## 0x7F800000 (11. Apr 2009)

faetzminator hat gesagt.:


> Abgesehen davon, dass dies eine relativ relative Aussage war, bin ich ein Schweizer


Ne, wo du konkret herkommst ist nicht so entscheidend, aber zu deiner verstörenden Aussage :lol: über die Rekursion ist mir irgendwie nichts besseres eingefallen 

Rekursion ist doch toll, versuche sonst mal irgendwelche klassisch rekursiven algos (sortierung mit mergesort, dfs auf graphen wie etwa auflistung von dateien in unterverzeichnissen oder zeichnen der gui-componenten, einfaches top down parsing usw...) iterativ umzuschreiben: da kommst du doch in schleifen und stacks um


----------



## Landei (11. Apr 2009)

```
if(x.charAt(i) == 'a' || x.charAt(i) == 'e' || x.charAt(i) == 'i' || x.charAt(i) == 'o' || x.charAt(i) == 'u'){...}
```

Meint ihr das *ernst*???

Warum zum Geier nicht das:


```
if("aeiou".contains(x.charAt(i))){...}
```


----------



## Schandro (11. Apr 2009)

an den TO:
Man sollte immer {...} Blöcke nach if, for, switch usw... statements benutzen. Wenn danach nur eine Anweisung kommt, kann man die {  } zwar theoretisch weglassen, es verstöst aber erstens gegen die Coding Convention und zweitens ist es eine potentielle Fehlerquelle...

Außerdem: Es ist schöner wenn innerhalb des algorithmus nicht die gesuchten zeichen ansich vorkommen, sondern man eine externes "Datenquelle" hat, z.b. ein Array als Membervariable der Klasse auf das er zugreift. Dadurch muss der Algorithmus ansich nicht geändert werden wenn er plötzlich was anderes suchen soll als Vokale.


----------



## JohannisderKaeufer (11. Apr 2009)

Um Vokale in einem String zu zählen, möchte man in der Regel eine Methode haben, die nur den Parameter String übergeben bekommt. Alles andere verleitet dazu unfug zu machen. Der Code des TO liefert für zaehleVokale("Bla",0,0) nicht unbedingt das gewünschte Ergebnis. Und derjenige der die Methode verwendet, ist nicht unbedingt derselbe der die Methode geschrieben hat.

Bei Rekursion ist es nicht das Hauptziel Variablen zum iterieren mitzuschleppen. Bei Rekursion, sollte man an Head und Tail denken, nicht wie ich Variablen mitschleppe um zu wissen wo ich gerade bin.


```
package vokaleZaehlen;

public class VokaleZaehler {

	public static int zaehleVokale(String string) {
		if(string.length()==0){
			return 0;
		}
		if (string.length() == 1) {
			if ("aieou".contains(string.toLowerCase())) {
				return 1;
			} else {
				return 0;
			}
		}
		return zaehleVokale(string.substring(0, string.length() / 2))
				+ zaehleVokale(string.substring((string.length() / 2)));
	}

	public static void main(String[] args) {
		String[] strings = { "a", "z", "az", "zzz", "azo", "zzzz","aaaa","aeiou s" ,""};
		for (String current : strings) {
			System.out.println(current + " " + zaehleVokale(current));
		}
	}
}
```


----------



## Marco13 (11. Apr 2009)

Sowohl bei den Aussagen als auch beim Code stimme ich mal weitgehend zu - bis auf eine Kleinigkeit: Dieses "Divide and Conquer" ist IMHO überflüssig....

Und ansonsten...

```
public static int countVowels(String s)
    {
        return s.length()==0?0:("aieouAEIOU".indexOf(s.charAt(0))<0?0:1)+countVowels(s.substring(1));
    }
```


----------



## 0x7F800000 (11. Apr 2009)

Marco13 hat gesagt.:


> Dieses "Divide and Conquer" ist IMHO überflüssig....


Master-Theorem ? Wikipedia
a=2 b=2 f(n)<O(1)<O(n) =>  T(n)<O(n)
Hier ist es also auch mit D&C linear...

Außerdem entspricht das nicht JohannisderKaeufer's eigenen vorschlag and Head-Tail zu denken 

Und überhaupt: substring ist relativ teuer. Lieber am anfang alles in StringBuilder rüberkopieren und dann immer den ersten buchstaben löschen, dann werden nicht dauernd neue immutable Strings erzeugt, sonst läuft's in O(n²)


----------



## ModellbahnerTT (11. Apr 2009)

0x7F800000 hat gesagt.:


> Und überhaupt: substring ist relativ teuer. Lieber am anfang alles in StringBuilder rüberkopieren und dann immer den ersten buchstaben löschen, dann werden nicht dauernd neue immutable Strings erzeugt, sonst läuft's in O(n²)


Nur kurz als Ergänzung, bevor jemand den Schwachsinn glaubt: substring() ist natürlich alles andere als "teuer", im Gegensatz zu einem delete in einem StringBuilder! Darum ist die Lösung von oben schon ganz richtig.


----------



## hdi (11. Apr 2009)

```
if("aeiou".contains(x.charAt(i))){...}
```

Vllt lacht ihr mich jetzt aus, aber das find ich genial. Hätte ich selber wohl auch niemals so geschrieben


----------



## 0x7F800000 (11. Apr 2009)

ModellbahnerTT hat gesagt.:


> Nur kurz als Ergänzung, bevor jemand den Schwachsinn glaubt: substring() ist natürlich alles andere als "teuer", im Gegensatz zu einem delete in einem StringBuilder! Darum ist die Lösung von oben schon ganz richtig.



ja ja, hast recht... hab da natürlich blödsinn erzählt 
string builder wird wohl auch nich auf doppelt verketteten listen basieren, sondern auf arrays. Da werden auch n-1 zeichen irgendwoher kopiert: bei substring in einen neuen string, bei builder werden sie um 1 verschoben... 
daher braucht man zum entfernen des ersten symbols auch O(n), das ist genauso scheiße wie substring... LinkedList müsste man da eigentlich nehmen... Aber dann ist es einfacher, den string in ruhe zu lassen und den aktuellen index weiterzureichen... 

Alles shice. Java ist eben darauf ausgelegt, dort wo es angebracht ist iteration einzusetzen, für solchen rekursiven kram sollte man prolog nehmn 

@hdi: bwuhaha


----------



## Spacerat (11. Apr 2009)

ModellbahnerTT hat gesagt.:


> Nur kurz als Ergänzung, bevor jemand den Schwachsinn glaubt: substring() ist natürlich alles andere als "teuer", im Gegensatz zu einem delete in einem StringBuilder! Darum ist die Lösung von oben schon ganz richtig.


100%ige Zustimmung... Man bekommt zwar eine Referenz (oder Zeiger owai) auf ein neues String-Objekt, dieses beinhaltet aber das Char-Array des vohergehenden Strings, nur mit anderen Start- und End-Pointern. StringBuilder ist in diesem Fall definitiv teurer.
@Edit: Ups... den Text habe ich verfasst, während 0x7F800000 zu seiner Einsicht kam...


----------



## 0x7F800000 (11. Apr 2009)

Spacerat hat gesagt.:


> 100%ige Zustimmung... Man bekommt zwar eine Referenz (oder Zeiger owai) auf ein neues String-Objekt, dieses beinhaltet aber das Char-Array des vohergehenden Strings, nur mit anderen Start- und End-Pointern. StringBuilder ist in diesem Fall definitiv teurer.
> @Edit: Ups... den Text habe ich verfasst, während 0x7F800000 zu seiner Einsicht kam...


So ist das sogar? 
Und was passiert dann mit dem speicher, wenn ich aus einem 10000zeichen-String ein 10zeichen-Substring rausschneide? Bleibt dann das char-array mit allen 10000 zeichen im speicher rumgeistern, weil er vom kleineren string referenziert wird oder wie? Oder kommen da wesentlich kompliziertere speicherverwaltungstaktiken zum einsatz, als ich es mir je gadacht hätte? :autsch:


----------



## Spacerat (11. Apr 2009)

@0x7F800000: Soweit man das überblicken kann sieht's wahrhaftig so aus. Nachlesen kann man es z.B. bei Guido Krüger, im Kapitel Performance-Tuning und man kann sich natürlich die "substring()"-Methoden in der API ansehen.


----------



## faetzminator (12. Apr 2009)

hdi hat gesagt.:


> ```
> if("aeiou".contains(x.charAt(i))){...}
> ```
> Vllt lacht ihr mich jetzt aus, aber das find ich genial. Hätte ich selber wohl auch niemals so geschrieben


Es ist von der Geschwindigkeit wundervoll, aber ich sag mir immer wider, dass ich nicht wegen der Geschwindigkeit Java programmiere, sondern weil ich (abgesehen davon, dass ich keine multiplen Vererbungen tätigen kann) schön OO programmieren kann.


----------

