Arraysumme

In diesem – für das Teile-und-Herrsche-Prinzip etwas künstliche – Problem soll die Summe aller Zahlen in einem Array aus Integer-Zahlen berechnet werden.

(A1)

Lade dir das Bluej-Projekt von https://codeberg.org/qg-info-unterricht/array-summe herunter.

Untersuche und teste den Konstruktor der Array-Klasse.

Implementiere die iterative Methode sumIterativ(), die mit Hilfe einer Schleife die Summe aller Array-Elemente berechnet.

Rekursion! Teile und herrsche...

Wie kann man dieses Problem rekursiv lösen? Zur Erinnerung:

Finde einen einfachen Fall, den du als Basisfall verwenden kannst.

Finde heraus, wie du die Aufgabe vereinfachen kannst, um zum Basisfall zu gelangen.

Was ist der direkt lösbare Basisfall für dieses Problem? Wie muss ein Array beschaffen sein, damit man die Summe aller Array Elemente unmittelbar erkennen kann?

Antwort:

Wenn das Array die Länge 0 oder 1 hat, ist das Ergebnis sehr einfach zu ermitteln: Im Falle des leeren Arrays ist die Summe 0, im Fall des Arrays mit der Länge 1 ist die Summe der Wert des einzigen Array-Elements.

Um das Teile-und-Herrsche Prinzip anwenden zu können muss man sich nun einen Rekursionsfall überlegen, der uns dem Basisfall, dem „Ziel“ des leeren Arrays immer näher bringt.

Wie kann man also beispielsweise die folgende Situation so verändern, dass die zur Summe aus kleineren Array(s) führt?

Antwort:

Zum Beispiel so:

Die Funktionsweise kann man also dem folgenden Flussdiagramm, entnehmen:

Das ist nun wieder eine klassische Rekursion, deren Aufrufe alle auf dem Call-Stack landen, bis der Basisfall erreicht ist. Erst dann können die vorigen Aufrufe abgeschlossen werden.