Neuling in Java - Seite 2

Tobias · Anmeldungsdatum: 15.02.2005 Beiträge: 149

Es gibt verschiedene Arten von Rekursionen.

Bei einer Endrekursion (hier wird das Ergebnis z.B. in einem Argument akkumuliert) wird nichts anderes getan als linear an die Tiefe zu gehen und am Schluß nur noch alle return-Befehle abzuklappern. Die Endrekursion wird von optimierten Compilern in Schleifen verwandelt.

Im Allgemeinen werden Rekursionen natürlich nicht in Schleifen übersetzt. (Was auch ohne komplexere Strukturen wie Heaps, Queues oder Stacks auch nicht möglich ist.

Aber deine Lösung scheint auch noch fehlerhaft. Was wäre z.B. bei den Strings

"12341234123412345" und "12345".

Dann merkt der Algo, dass die ersten Zeichen übereinstimmen und wird neu aufgerufen mit stringVergleich("2341234123412345", "2345", 4)

D.h. sobald an einer Stelle die ersten zeichen übereinstimmen wird der Suchstring gekürzt und steht nichtmehr ganz zur Verfügung.

jovi · Anmeldungsdatum: 04.04.2005 Beiträge: 4 Wohnort: München

Du hast natürlich vollkommen recht. Eigentlich wollte ich ja auch nur eine rekursive Lösung skizzieren. Also meine Verbesserung:
0) wenn Länge(array1) < zahl OR Länge(array2) < zahl dann return(false)
1) wenn die jeweils ersten zahl Zeichen der Strings gleich sind, dann return(true)
sonst return(stringVergleich(REST(array1), array2, zahl) OR stringVergleich(array1, REST(array2), zahl))

Nur die Lösung ist nun tatsächlich furchtbar ineffizient, da stringVergleich dauernd mit den selben Parametern aufgerufen wird. Um das Ganze auch effizient zu machen müsste man sich tatsächlich alle schon einmal durchlaufenen stringVergleich-Aufrufe
in einem globalen 2-dimensionalen Feld merken. Was Besseres fällt mir im Moment leider nicht ein.

Georg · Administrator Anmeldungsdatum: 15.02.2005 Beiträge: 57 Wohnort: Aachen

Hi,

da jede iterative Lösung besser ist als eine rekursive sollte sich das doch gut mit zwei for-Schleifen lösen lassen?

Da ich dieses Semester erst Java lerne, hier eine Lösung in Java-ähnlichem Pseudocode smile

kurellajunior · Administrator Anmeldungsdatum: 14.02.2005 Beiträge: 214 Wohnort: Berlin-Pankow

Das entspräche der "Holzhammer" methode von Tobias. Zudem war eine rekursive Lösung weiter unten gesucht Augenzwinkern

Und wenn Du weiterliest, gibt es einen iterativen Vorschlag mit nur einer Schleife von mir Augenzwinkern

Woher hast Du denn die Pauschalaussage, jede iterative Lösung sei besser als eine rekursive? Wenns Dich interessiert, mach dazu einen Thread in der theoretischen Informatik auf Augenzwinkern

genug gezwinkert, Jan

Georg · Administrator Anmeldungsdatum: 15.02.2005 Beiträge: 57 Wohnort: Aachen

Tatsächlich, die von mir dargebotene Lösung war ja schon da, allerdings gemein in theoretischen Aussagen versteckt.

Kurellajunior, hier können wir den Wettstreit iterativ gegen rekursiv ausdiskutieren.