Rekursion

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Rekursion
Hey,

ich bin an dem aktuellen Übungsblatt am Verzweifeln. Ich hab mir jetzt die Vorlesungsfolien zur Rekursion weiß gott wie oft durchgelesen, aber ich kann sie bei den aktuellen Fällen in 4.4 und 4.5 einfach nicht anwenden.
Andere Aufgaben, in denen Rekursion verlangt wurde, waren kein Problem, sowas wie Fakultät und Potenzmethoden auf rekursiver Basis sind ja kein Problem, die kann ich auch ohne weiteres.
Was mir bei den aktuellen Aufgaben Probleme bereitet, sind mehrere Dinge:

  1. Normal hat eine Rekursion ja eine Fallunterscheidung, die den Basisfall darstellt und eine fortführende Ausführung durch Aufrufen von sich selbst. Ich hab bei der 4.4 also Basisfall “if( i == ns.length) {return Integer.toString(ns[ i ])}”, weil falls mein i der letzte Arrayeintrag ist, besteht der Array ja nur aus diesem Wert. Aber wie komme ich weiter? Bei der Fallunterscheidung schaue ich, ob i < ns.length ist und wenn ja, will ich doch schauen, ob ns[ i ] und ns[i+1] gleich sind (z.b bei Array {1,1,3}) und dann addiere ich beide Werte. Nur weiß ich nicht, wo die Rekursion ins Spiel kommen soll und wie ich sie anwenden soll, ich sitz da jetzt schon Stunden ran und komm einfach nicht dahinter.
  2. Ich kann mit den Parametern bei den Methoden nix anfangen. Hier zum Beispiel eine beliebige rekursive Fakultätsberechnung:
	public static double factorial(int n){
		double erg = 1;
		if (n == 0) { erg = 1;
		} else { erg = factorial (n-1) * n; }
		return erg;
	}

Da weiß ich ja, was mein Parameter darstellt und wie ich auf ihn im Methodenaufruf im “else”-Fall zugreifen muss, um das Ergebnis zu erzeugen, aber, wie gesagt, mit den Parametern aus 4.4 und 4.5 kann ich rein gar nichts anfangen.

3

Tafel-/Rechnerübung schon besucht?
Die Intensivübung morgen beschäftigt sich auch nochmal mit Rekursion (insbesondere Backtracking).

4

Ich prophezeihe mal eine IndexOutOfBoundException ;). Überlege dir mal, wo du mit dem Zählen beim Array beginnst und wo sich somit wirklich dein letztes Arrayelement befindet.

Ich dachte das fängt dein Basisfall schon ab? Wenn dein Programm bis dahin kommt gilt sicher i < ns.length.

Naja was du da beschreibst klingt ja egtl. ganz gut. Aber du sollst die Rekursion hier einfach nutzen, um über das ganze Array drüber zu laufen. Du beschreibst ja nur einen Schritt für ein/zwei Elemente des Arrays. Die Rekursion sorgt dafür, dass alle Arrayelemente behandelt werden.

Kannst du die Frage konkretisieren? Denn gerade bei der 4.4 wird im Aufgabenblatt egtl. sehr genau beschrieben, wozu die Parameter gut sind:

Du hast als Parameter also dein Array, das du durchlaufen sollst und einen Index, der angibt an welcher Stelle du dich im Array gerade befindest. Mit Hilfe dieses Indexwertes kannst du dich durch rekursive Aufrufe durch dein Array bewegen.