Informatik
Startseite > Unterricht > Algorithmen und Datenstrukturen > Rekursion


Beispiel 1: Gezähltes Händeschütteln

Aufgabe: Auf einer Geburtstagsgesellschaft sind n Gäste anwesend. Jede Person gibt jeder anderen genau einmal die Hand. Welches ist die Häufigkeit des Händeschüttelns h(n) in Abhängigkeit von n?

Lösung: Wir verfahren gemäß der Maxime "Führe die Aufgabe auf eine einfachere Version ihrer selbst zurück!" Das heißt, wir bestimmen h(n) dadurch, dass wir annehmen, h(n - 1) sei bereits bekannt - und nun trifft der n-te Gast ein. Die Hand wie vieler Personen muss er schütteln? Natürlich die von n - 1 Personen. Also gilt h(n) = h(n - 1) + n - 1.

Welches ist der unmittelbar lösbare Fall? Das ist h(1) = 0, denn ist nur 1 Gast anwesend, kann er keinem anderen Gast die Hand schütteln. Also gilt:

h(n) = wenn n = 1 dann 0 sonst h(n - 1) + n - 1.

In Java:

  static int h (int n) {
    if (n <= 1)
      return 0;
    else
      return h(n - 1) + n - 1;
    } // Ende h

Das Gesamtprogramm lautet:

(...)

Beispieldialog:

> java Hände

Gezaehltes Haendeschuetteln
---------------------------

Anzahl der Gäste: 10
h(10) = 45