Lernziele

  • Sie können den Begriff Algorithmus erklären
  • Sie können Probleme anhand der vorgestellten Systematik lösen
  • Sie verstehen die Idee der Rekursion
  • Sie können einfache Rekursion implementieren, z.B. indem Sie ein iteratives Verfahren in eine rekursive Version umwandeln
Neueste Aktualisierungen (zuletzt 02.10.2021)
  • 02.10.2021: Lernziele angepasst
  • 02.08.2021: Neue Kapitelnummerierung

In diesem Kapitel lernen Sie, Probleme systematisch anzugehen.

E1.1 Was ist ein Algorithmus?

Ein Algorithmus ist eine Art Kochrezept, um ein Problem zu lösen. Wollen Sie z.B. Kaffee kochen, müssen Sie bestimmte Schritte befolgen:

  1. Filter einsetzen
  2. Kaffee einfüllen
  3. Maschine einschalten

Natürlich kann es sein, dass kein Wasser mehr in der Maschine ist - das sollten Sie in Ihr Rezept einbauen:

  1. Filter einsetzen
  2. Kaffee einfüllen
  3. Wenn kein Wasser in der Maschine ist, dann
    • Wasser einfüllen
  4. Maschine einschalten

Der Schritt "Kaffee einfüllen, besteht eigentlich aus vielen Teilschritten, die wir genauer aufführen könnten

  1. Filter einsetzen
  2. Tu das folgende 3 Mal:
    • Löffel mit Kaffeepulver befüllen
    • Löffel im Filter ausleeren
  3. Wenn kein Wasser in der Maschine ist, dann
    • Wasser einfüllen
  4. Maschine einschalten

Sie sehen natürlich sofort, dass ein Algorithmus so ähnlich aussieht wie Processing-Code. Es gibt einfache Schritte, das einspricht einem Befehl (= Funktionsaufruf) in Processing. Und es gibt If-Anweisungen und Schleifen. Ihr Code löst andere Probleme, zum Beispiel das Problem, einen Ball zu bewegen und dabei darauf zu achten, dass der Ball korrekt von der Wand abprallt. Oder Ihr Code löst das Problem, einen Mittelwert zu berechnen, oder ein Sonnensystem zu animieren.

In nächsten Abschnitt schauen wir uns an, wie wir Algorithmen finden.

E1.2 Probleme lösen

Um ein Problem zu lösen, sollten Sie sich zunächst vor Augen führen, welche Daten Sie als Ausgangsbasis haben, das ist Ihr Input. Dann fragen Sie sich, was das Ziel Ihres Problems ist, d.h. was ist der gewünschte Output?

Im nächsten Schritt müssen Sie Ideen generieren, wie Sie das Problem in einem Programm lösen könnten. Sie sammeln Methoden (Hilfsvariablen, If-Anweisungen, Schleifen), die Ihrem Gefühl nach dabei eine Rolle spielen könnten.

Schließlich schreiben Sie Pseudo-Code. Das ist wie ein Programm, aber ganz informell formuliert. Erst dann gehen Sie an die Umsetzung - das nennt man auch Implementierung.

Der letzte Schritt besteht im Testen. Ihr Programm muss sich nicht nur starten lassen, sondern muss auch für alle möglichen Inputs die korrekte Lösung liefern. Natürlich können Sie nicht alle Möglichkeiten durchtesten, aber es ist wichtig, möglichst alle Extremfälle beispielhaft zu testen. Was sind Extremfälle? Wenn Sie einen Suchalgorithmus schreiben, der ein bestimmtes Element in einem Array finden muss, dann testen Sie den Fall, dass...

  • ... das Suchergebnis ganz vorne ist
  • ... das Suchergebnis ganz hinten ist
  • ... das Array leer ist

Wir sehen uns das anhand von Beispielen an:

Beispiel 1: Summe berechnen

Aufgabe: Berechene die Summe 1 + 2 + ... + N

Schritt 1 (Input): Die Zahl N

Schritt 2 (Output): Die Summe 1 + 2 + ... + N

Schritt 3 (Grundidee): Schritt für Schritt durch die Elemente gehen und das aktuelle Element zu einem Zwischenergebnis hinzuzählen. Am Schluss ist das Zwischenergebnis auch das Endergebnis.

Schritt 4 (Methoden) Schleife zum Durchlaufen, Variable für das Zwischenergebnis

Schritt 5 (Pseudo-Code)

  1. Neue Variable result
  2. Schleife mit Laufvariable i von 1 bis N:
    • result = result + i
  3. Variable result enthält die Summe

Schritt 6 (Umsetzung) Jetzt können wir das ganze in Code umsetzen, z.B. indem wir eine Funktion schreiben, die als Eingabeparameter das N bekommt:

int sum(int n) {
   int result = 0;
   for (int i = 0; i <= n; i++) {
      result = result + i;
   }
   return result;
}

Schritt 7 (Testen) Zum Testen sollten Sie sich den Spezialfall N=0 ansehen:

void setup() {
  println(sum(0));
  println(sum(5));
}
0
15

Es funktioniert also. Warum funktioniert N=0 eigentlich?

Noch ein Beispiel:

Beispiel 2: Finde das kleinste Element

Aufgabe: Finde in einem Array die kleinste Zahl

Schritt 1 (Input): Array a (int)

Schritt 2 (Output): Eine Zahl (int), die kleinste in a

Schritt 3 (Grundidee): Schritt für Schritt durch die Elemente gehen und prüfen, ob das aktuelle Element das kleinste ist. Wir müssen uns das aktuell kleinste merken. Zu Beginn ist das kleinste Element einfach das erste Element.

Schritt 4 (Methoden) Schleife zum Durchlaufen, Variable für das aktuell kleinste Element

Schritt 5 (Pseudo-Code)

  1. Neue int-Variable smallest = a[0]
  2. Schleife mit Laufvariable i von 1 bis (Länge von a - 1):
    • Wenn smallest > a[i] dann smallest = a[i]
  3. Variable smallest enthält kleinstes Element

Schritt 6 (Umsetzung) Wir setzen das um, indem wir eine Funktion schreiben, die als Eingabeparameter den Array a bekommt:

int smallest(int[] a) {
   int smallest = a[0];
   for (int i = 1; i < a.length; i++) {
      if (smallest > a[i]) {
      	smallest = a[i];
      }
   }
   return smallest;
}

Schritt 7 (Testen) Wir testen unsere Funktion mit einem "normalen" Array und dann mit einem Extremfall: ein leeres Array.

void setup() {
  int[] foo = { 10, 30, -20, 100 };
  println(smallest(foo));

  int[] boo = new int[0]; // Array mit null Elementen
  println(smallest(boo));
}

Beim Array boo meldet Processing eine ArrayIndexOutOfBoundsException, d.h. unser Code ist nicht ganz wasserdicht. Wir müssen den Fall abfangen, dass das Array die Länge 0 hat (keine Elemente):

int smallest(int[] a) {
   if (a.length == 0) {
   	return 0; // Bei Länge 0 wird zurückgesprungen
   }
   int smallest = a[0];
   for (int i = 1; i < a.length; i++) {
      if (smallest > a[i]) {
      	smallest = a[i];
      }
   }
   return smallest;
}

Jetzt funktioniert unser Test:

-20
0

Die Lösung ist nicht ideal, da derjenige, der die Funktion aufruft, nicht weiß, ob das Array im zweiten Aufruf oben leer war oder ob 0 tatsächlich das kleinste Element eines nicht-leeren Arrays war. Eine bessere Lösung können wir erst nächstes Semester mit Hilfe von Exceptions formulieren.

Noch ein "Klassiker":

Beispiel 3: Tausche zwei Elemente in einem Array

Aufgabe: Tausche zwei Elemente in einem Array

Schritt 1 (Input): Array a (int) und zwei Indices x und y der Elemente, die getauscht werden sollen

Schritt 2 (Output): Der selbe Array a, nur dass die zwei Elemente vertauscht sind

Schritt 3 (Grundidee): Beide Werte abrufen und in den jeweils anderen Index speichern

Schritt 4 (Methoden) Einen Wert müssen wir in einer Variablen zwischenspeichern

Schritt 5 (Pseudo-Code)

  1. Neue Variable temp
  2. temp = a[x]
  3. a[x] = b[y]
  4. b[y] = temp

Schritt 6 (Umsetzung) Wir setzen das um, indem wir eine Funktion schreiben, die als Eingabeparameter den Array a bekommt und die zwei Indices und dann a manipuliert:

void switchElements(int[] a, int x, int y) {
   int temp = a[x];
   a[x] = a[y];
   a[y] = temp;
}

Was Sie stutzig machen sollte ist, dass die Funktion keinen Rückgabewert hat. In der Tat modifizieren Sie den Array direkt innerhalb der Funktion, obwohl das Array doch ein Parameter ist! Wir sehen das beim Testen.

Schritt 7 (Testen) Zunächst ein "normaler" Test:

void setup() {
  int[] a = { 3, 2, 1 };
  println("vorher");
  println(a);

  switchElements(a, 0, 2); // tauschen

  println("nachher");
  println(a);
}
vorher
[0] 3
[1] 2
[2] 1
nachher
[0] 1
[1] 2
[2] 3

Bei komplexen Objekten wie Arrays oder eben Objekten ist es durchaus üblich, dass der Array (bzw. das Objekt) in der Funktion verändert wird. Dennoch ist natürlich Vorsicht beim Gebrauch solcher Funktionen angesagt, denn das, was Sie reingeben (Array a), sieht hinterher anders aus.

Wir testen noch einen Extremfall: Ein Array mit einem Element, bei dem wir dies eine Element mit sich selbst vertauschen:

void setup() {
  int[] a = { 1 };
  println("vorher");
  println(a);
  switchElements(a, 0, 0);
  println("nachher");
  println(a);
}

Läuft einwandfrei:

vorher
[0] 1
nachher
[0] 1

Wie sieht es aus, wenn man Elemente tauschen will, die gar nicht im Array sind, d.h. einer der Indices ist außerhalb der Array-Grenzen?

void setup() {
  int[] a = { 1 };
  println("vorher");
  println(a);
  switchElements(a, 0, 1);
  println("nachher");
  println(a);
}

Hier bekommen wir wieder eine ArrayIndexOutOfBoundsException. Ob man diesen Fall explizit abfangen muss, ist Ansichtssache. Sie können ja mal überlegen, wie Sie das Abfangen einbauen würden.

Zum Abschluss ein etwas komplexeres Beispiel:

Beispiel 4: Sortieren

Aufgabe: Verändere ein Array so,
dass es aufsteigend sortiert ist

Schritt 1 (Input): Array a (int)

Schritt 2 (Output): Array a (int), aufsteigend sortiert

Schritt 3 (Grundidee): Alle Elemente von a durchlaufen. Sicherstellen, dass aktuelles Element nicht kleiner ist, als diejenigen, die vor dem Element stehen. Sonst tauschen.

Schritt 4 (Methoden) Wir benutzen eine Schleife, um die Elemente zu durchlaufen und eine zweite Schleife, um das Element mit allen Vorgängern zu vergleichen. Außerdem nutzen wir unsere Funktion "switchElement" von oben.

Schritt 5 (Pseudo-Code)

  1. Schleife mit Laufvariable i von 0 bis (Länge von b - 1):
    • //aktuelles Element a[i] mit allen vorangestellten vergleichen
      Schleife mit Laufvariable k von 0 bis (i - 1):
      • Wenn a[i] (aktuelles Element) kleiner ist als a[k] (ein vorangestelltes Element), dann tausche die beiden mit Funktion switchElement
  2. Ergebnis steht in Array a (der jetzt verändert ist!)

Schritt 6 (Umsetzung) Wir setzen das um, indem wir eine Funktion schreiben, die als Eingabeparameter den Array a bekommt und keinen Rückgabewert hat. Array a wird durch die Funktion direkt verändert.

void sortArray(int[] arr) {
  for (int i = 0; i < arr.length; i++) {
    for (int k = 0; k < i; k++) {
      if (arr[i] < arr[k]) {
        switchElements(arr, i, k);
      }
    }
  }
}

Schritt 7 (Testen) Erstmal ein ganz "normales" Beispiel:

void setup() {
  int[] a = { 2, 3, -1, 1 };
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}
vorher
[0] 2
[1] 3
[2] -1
[3] 1
nachher
[0] -1
[1] 1
[2] 2
[3] 3

Was wären "Extremfälle"? Zum Beispiel, dass das Array bereits sortiert ist...

// Fall: Array richtig sortiert
void setup() {
  int[] a = { 1, 2, 3 };
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}
vorher
[0] 1
[1] 2
[2] 3
nachher
[0] 1
[1] 2
[2] 3

... oder dass es genau "falschrum" sortiert ist ...

// Fall: Array falschrum sortiert
void setup() {
  int[] a = { 3, 2, 1 };
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}
vorher
[0] 3
[1] 2
[2] 1
nachher
[0] 1
[1] 2
[2] 3

... und natürlich, dass es leer ist.

// Fall: Array ist leer
void setup() {
  int[] a = new int[0];
  println("vorher");
  println(a);

  sortArray(a);

  println("nachher");
  println(a);
}
vorher
nachher

E1.3 Rekursion

Rekursion ist eine Methode, um Algorithmen zu implementieren, die darauf basiert, dass eine Funktion F sich selbst wiederholt aufruft, um ein Problem zu lösen.

Damit das funktioniert, muss Funktion F das Problem P, das es zu lösen gilt, in zwei Teile (P1 und P2) aufteilen. P1 ist dabei ein triviales Problem, das direkt von F gelöst wird, P2 ist so ähnlich wie P, aber "kleiner" und wird durch einen weiteren Aufruf von F auf P2 gelöst. Klingt wie Magie? Funktioniert aber!

Einfaches Beispiel

Schauen wir uns ein einfaches Beispiel an: Die Funktion printHashes() soll eine per Parameter spezifizierte Anzahl von Hash-Zeichen auf der Konsole ausgeben. Die einer Schleife würden Sie das so implementieren:

void setup() {
  printHashes(5);
}

void printHashes(int num) {
  for (int i = 0; i < num; i++) {
    print("#");
  }
}

Eine rekursive Version von printHashes()basiert auf folgender Einsicht: Das Problem P = "drucke 5 Hash-Zeichen" lässt sich in die zwei Teilprobleme P1 und P2 zerlegen:

  • P1: Drucke 1 Hash-Zeichen (trivial)
  • P2: Drucke 4 Hash-Zeichen (ähnliches, aber "kleineres" Problem)

Das erste Problem löst man direkt durch ein einziges print(), für das zweite Problem ruft man die gleiche Funktion mit dem Parameter 4 auf. Bei diesem Aufruf wird wieder ein Hash gedruckt und die Funktion mit Parameter 3 aufgerufen...

printHashes(5)
printHashes(4)
printHashes(3)
...

Jetzt müssen wir noch aufpassen, dass wir nicht in eine Art Endlosschleife verfallen. Denn wenn printHashes() mit dem Parameter 1 aufgerufen wird, wollen wir ja nicht printHashes im Anschluss mit 0 aufrufen (und dannach mit negativen Zahlen).

...
printHashes(1)
printHashes(0)
printHashes(-1)
printHashes(-2)
...

Wir müssen also den Basisfall abfangen, dass nur nur 1 Hash-Zeichen gedruckt wird, denn hier ist das Problem P identisch mit dem (trivialen) Teilproblem P1 und wir müssen die Funktion kein weiteres Mal aufrufen.

Im Code sieht die Funktion wie folgt aus:

void printHashes(int num) {
  // Teilproblem P1 direkt lösen
  print("#");

  // Ausschließen, dass dies der Basisfall ist
  if (num > 1) {

    // Teilproblem P2 durch Rekursion lösen
    printHashes(num - 1);

  }
}

Dies Beispiel diente nur der Erklärung. Die Lösung mit der Schleife nennt man auch ein iteratives Verfahren, die zweite Lösung ist dann das rekursive Verfahren.

Im vorliegenden Fall ist sicher das iterative Vorgehen vorzuziehen, denn Rekursion hat einige Nachteile:

  • Fehleranfällig: Durch die ungewohnte Art des Programmierens entstehen leicht Fehler, z.B. dass man den Basisfall nicht abfängt.
  • Performanz: Für jeden Funktionsaufruf muss eine Programmiersprache bestimmte Verwaltungsinformationen anlegen, damit nach Abarbeitung der Funktion auch alles korrekt abläuft. Das bedeutet, dass die iterative Methode um einiges schneller ist und weniger Speicherplatz verbraucht.

Jetzt fragen Sie sich, warum man sich überhaupt mit Rekursion beschäftigen muss? Es gibt ein paar Probleme, bei denen die rekursive Methode tatsächlich einfacher zu programmieren ist als die iterative Methode. Zwei typische Bereiche sind Sortieren und Suchen, beides enorm wichtige Aufgaben in der Programmierung, auch schon vor dem Zeitalter von Google. Dass hier Rekursion zum Zuge kommt, hat auch damit zu tun, dass sich Baumstrukturen sehr leicht und intuitiv mit Rekursion durchlaufen lassen und Bäume gehören zu den wichtigsten Strukturierungsmethoden in der Informatik überhaupt. Zum Beispiel bilden Verzeichnisse, Unterverzeichnisse und Datein einen Baum. Weiteres Beispiel sind Struktur und Inhalte einer Webseite (Texte, Überschriften, Bilder, Links etc.) als Baum strukturiert (das sog. document object model oder DOM).

Beispiele mit Rückgabe

Schauen wir uns ein etwas weniger triviales Beispiel an. Wir wollen jetzt die Summe 1 + 2 + .. + N berechnen.

Wieder hätten wir eine relativ leichte iterative Variante im Angebot:

void setup() {
  println(summeBis(5));
}

// Iterative Lösung

int summeBis(int ende) {
  int summe = 0;
  for (int i = 1; i <= ende; i++) {
    summe = summe + i;
  }
  return summe;
}
15

Wir überlegen uns wieder, wie wir das Problem P = "Summe von 0 bis N" zerlegen. Wir nehmen "0 bis N" statt "1 bis N", weil die Formulierung dann etwas eleganter ausfällt.

  • P1: Addiere N zu der Teilsumme 0 bis (N-1)
  • P2: Berechne die Teilsumme 0 bis (N-1)

Im Gegensatz zum ersten Beispiele, müssen wir bei P1 die Lösung von P2 verwenden. Außerdem müssen wir uns überlegen, was hier der Basisfall ist. Die Rekursion soll enden, wenn wir die Summe bis 0 berechnen sollen (ist natürlich 0).

Als Code:

int summeBis(int ende) {

  // Basisfall
  if (ende == 0) {
    return 0;
  }

  // Löse P2 durch Rekursion:
  int erg = summeBis(ende - 1);

  // Löse P1 mit Ergebnis von P2
  return ende + erg;
}
15

Oder etwas kompakter geschrieben:

int summeBis(int ende) {

  // Basisfall
  if (ende == 0) {
    return 0;
  }

  // Löse P1 und P2
  return ende + summeBis(ende - 1);
}

Der Gründlichkeit halber sollten wir uns überlegen, was passiert, wenn man die Funktion mit 0 oder negativen Werten aufruft: Hier würden wir in einen unendlichen Regress laufen. Also fangen wir diese Fälle ab:

int summeBis(int ende) {

  if (ende <= 0) {
    return 0;
  }

  return ende + summeBis(ende - 1);
}
	

Ein weiteres (klassisches) Beispiel für Rekursion ist die Berechnung der "Fakultät" einer Zahl. Die Fakultät von 5 wird auch 5! geschrieben und ist definiert durch:

	5! = 1 * 2 * 3 * 4 * 5 = 120

Für die rekursive Lösung überlegen wir wieder, wie wir das Problem P, die Fakultät für eine Zahl n zu berechnen zerlegen:

  • P1: Multipliziere n mit der Fakultät von n-1
  • P2: Berechne die Fakultät von n-1

Schließlich überlegen wir uns noch den Basisfall: Die Fakultät von 0 ist als 1 definiert. Hier darf nicht mehr die Funktion für n-1 aufgerufen werden!

Als Code:

void setup() {
  println(fak(5));
}

int fak(int n) {

  // Basisfall
  if (n == 0) {
    return 1;
  }

  // Teilprobleme P1 und P2
  return n * fak(n - 1);
}
120

Auch hier sollten wir überlegen, was passiert, wenn jemand negative Werte übergibt (für negative Werte ist Fakultät nicht definiert), damit unsere Funktion nicht in einen unendlichen Regress geht. Wir geben in diesen Fällen einfach eine 0 zurück.

int fak(int n) {

  // Fehlerfall
  if (n < 0) {
    return 0;
  }

  // Basisfall
  if (n == 0) {
    return 1;
  }

  // Teilprobleme P1 und P2
  return n * fak(n - 1);
}

Beispiel mit Array

Rekursion wird i.d.R. bei größeren Datenstrukturen angewandt, z.B. bei Arrays, die sortiert werden müssen oder in denen etwas gesucht wird.

Sehen wir uns zunächst wieder eine einfache Aufgabe an, die wir ohne weiteres mit einer Schleife - also iterativ - lösen könnten. Wir wollen alle Zahlen eines int-Arrays addieren.

Unsere zwei Teilprobleme sind hier:

  • P1: Addiere Element 0 mit der Summe der Elemente 1 bis (N-1)
  • P2: Berechne die Summe der Elemente 1 bis (N-1)

Ein erster Entwurf könnte so aussehen:

void setup() {
  int[] num = {5, 8, 4, 20, 1, -7 };
  println(summe(num));
}

int summe(int[] arr) {
  if (arr.length == 0) {
    return 0;
  }
  return arr[0] + summe(subset(arr, 1));
}

Wir wenden unsere Funktion summe rekursiv auf immer kürzere Teilarrays an, die wir mit subset erzeugen. Das Problem mit subset ist, dass hier immer ein komplett neues Array erzeugt wird (verbraucht Speicher) und dieses neue Array mit Hilfe des ursprünglichen Arrays befüllt wird (verbraucht Zeit). Also für größere Arrays eine reichlich ineffiziente Lösung.

Um das ganze effizienter zu lösen, müssen wir nicht nur den Array übergeben, sondern einen Parameter einführen, der den Startindex definiert.

void setup() {
  int[] num = {5, 8, 4, 20, 1, -7 };
  println(summeAb(num, 0));
}

int summeAb(int[] arr, int start) {
  if (start >= arr.length) {
    return 0;
  }
  return arr[start] + summeAb(arr, start + 1);
}

Wenn wir möchten, können wir jetzt die Funktion summe definieren, die man verwenden sollte:

int summe(int[] arr) {
  return summeAb(arr, 0);
}

Mergesort

Ein komplexeres Beispiel ist das Sortieren mittels "Mergesort". Mergesort basiert auf der Erkenntnis, dass folgendes Problem "Merge" leicht und effizient lösbar ist. Dieses Problem wird nicht rekursiv gelöst. Der rekursive Anteil von Mergesort kommt später.

Merge

Problem: Gegeben zwei bereits sortierte Arrays, erzeuge einen zusammengefügten Array, der ebenfalls sortiert ist.

Beispiel: Gegeben die sortierten Arrays a = { 2, 5 } und b = { 3, 10 }, stelle einen Array der Länge 4 her, der die Elemente von a und b in sortierter Folge enthält. In diesem Fall also { 2, 3, 4, 10 }.

Warum ist das Problem leicht? Weil Sie mit gleichzeitig durch die zwei Arrays a und b wandern und jeweils die kleinere Zahl in einen neuen Array r schieben.

int[] merge(int[] a, int[] b) {
  int[] r = new int[a.length + b.length];

  int ai = 0;
  int bi = 0;

  for (int ri = 0; ri < r.length; ri++) {
    if (ai < a.length && bi < b.length) {
      if (a[ai] < b[bi]) {
        r[ri] = a[ai];
        ai++;
      } else {
        r[ri] = b[bi];
        bi++;
      }
    } else {
      if (ai >= a.length) {
        r[ri] = b[bi];
        bi++;
      } else {
        r[ri] = a[ai];
        ai++;
      }
    }
  }
  return r;
}

Mergesort

Da wir das Problem "Merge" gelöst haben, können wir folgende Strategie anwenden, um den Array c der Länge N zu sortieren. Wir unterscheiden wieder zwischen dem "trivialen" Teilproblem P1 und dem rekursiv zu lösenden Teilproblem P2:
  • P2: Sortiere die zwei Hälften von c mit mergesort(). Die Hälften haben jeweils die Länge N/2, d.h. das Problem verkleinert sich erheblich.
  • P1: Führe die zwei sortierten Hälften mit merge() zusammen.

Der Basisfall ist der Fall, dass der zu sortierende Array die Länge 1 hat. Dann wird der Array einfach wieder zurückgegeben.

Wir können uns das am Array { 4, 3, 2, 1 } vor Augen führen.

Mergesort

Als Code:

int[] mergesort(int[] arr) {

  // Basisfall
  if (arr.length <= 1) {
    return arr;
  }

	// P2: Rekursiver Aufruf von mergesort
  // Dazu den Array teilen...
  int mitte = arr.length/2;
  int[] arr1 = subset(arr, 0, mitte);
  int[] arr2 = subset(arr, mitte);

  // ...und die Teilarrays sortieren
  int[] sarr1 = mergesort(arr1);
  int[] sarr2 = mergesort(arr2);

  // P1: Zusammenführung mit merge
  int[] result = merge(sarr1, sarr2);

  return result;
}

Beachten Sie, dass auch ein Array mit ungerader Anzahl kein Problem darstellt. Ein Array { 3, 2, 1 } wird in die zwei "Hälften" { 3 } und { 2, 1 } geteilt.

Übungsaufgaben

E1.3 a) Potenzieren

Schreiben Sie die Funktion hoch(basis, exponent), die das Ergebnis der Operation basis^exponent zurückgibt. Dabei sollen Parameter und Rückgabewert vom Typ int sein.

Lösen Sie das Problem per Rekursion und nicht iterativ (also nicht mit einer Schleife).

Testen Sie Ihren Code z.B. mit

void setup() {
  println(hoch(5, 2));
  println(hoch(3, 3));
}
25
27

E1.3 b) For-Schleife

Programmieren Sie zu reinen Übungszwecken eine For-Schleife rekursiv. Genauer gesagt ist das Ziel, von z.B. 0 bis 4 zu laufen und immer die Laufzahl auszudrucken. Sie sollen auch die Schrittweite (step) kontrollieren sollen, also ob man in 1er, 2er oder sonstigen Schritten durch die Schleife läuft.

Schreiben Sie die Funktion recursiveFor mit drei Parametern für den Start (z.B. 0), das Ende (z.B. 5, dann soll man bis 4 laufen) und die Schrittweite (z.B. 1).

Testen Sie Ihr Programm mit

void setup() {
  recursiveFor(0, 5, 1);
  println();
  recursiveFor(2, 6, 2);
}

Sie sollten sehen:

0
1
2
3
4

2
4

E1.3 c) Sierpinski-Dreieck *

Programmieren Sie die Darstellung eines Sierpinski-Dreiecks (einem Fraktal) per Rekursion. Bei diesem Dreieck werden aus einem Dreieck immer wieder weiße Teile "rausgestanzt". Sie können das am Beispiel unten ausprobieren und gern auch den Wikipedia-Eintrag lesen.

Dazu benötigen Sie lediglich eine Funktion sierpinski mit sechs Parametern für die drei Eckpunkte des fraglichen Dreiecks. Sie benötigen einen weiteren Parameter (ich habe ihn depth genannt), um die Rekusion zu stoppen.

(Interaktives Feld: Erst anklicken, dann mit Cursortasten)

E1.3 d) Maximum finden

Schreiben Sie eine Funktion, die das Maximum eines Arrays von Zahlen findet.

Lösen Sie das Problem mit einer einzigen Funktion maxRecur(), die einen int-Array bekommt und das Maximum zurückgibt.

Nutzen Sie die Processing-Funktion subset(), die Sie in der Processing-Referenz finden.