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 eine Person kann niemand anderem 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:

import java.io.*;

class Hände {
  // demonstriert lineare Rekursion

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

  static void main (String xy[]) throws IOException {

    InputStreamReader lies = new InputStreamReader(System.in);
    BufferedReader    eing = new BufferedReader(lies);

    System.out.println("\nGezaehltes Haendeschuetteln");
    System.out.println("------------------------\n");

    System.out.print("Anzahl der Gäste: ");
    int gästezahl = Integer.parseInt(eing.readLine());

    System.out.println("h(" + gästezahl + ") = " + h(gästezahl));

    } // Ende main
  } // Ende Hände

Beispieldialog:

> java Hände

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

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