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 hDas Gesamtprogramm lautet:
(...)
Beispieldialog:
> java Hände
Gezaehltes Haendeschuetteln
---------------------------Anzahl der Gäste: 10
h(10) = 45