\begin{slide}{Unterprogramme: Türme von Hanoi}

\begin{itemize}
\item
  drei Türme $A,B,C$.
\item
  anfangs auf $A$ die Scheiben $[32, 31, \ldots, 2,1]$, $B$ leer, $C$ leer. 
\item
  gesucht: eine Folge von Bewegungen \emph{einzelner} Scheiben, 
  so daß:
\item
  niemals eine größere über einer kleineren liegt
\item
  und schließlich alle auf $B$ liegen.
\end{itemize}

\end{slide}

\begin{slide}{Türme von Hanoi: Entwurf}

Spezifikation (Schnittstelle) einer Prozedur
\begin{verbatim}
static void hanoi 
    (int s, String v, String n, String h)
\end{verbatim}
soll Folge der Bewegungen drucken,
die nötig sind, um Scheiben $[s, s-1,\ldots, 2,1]$
von Turm \verb|v| nach Turm \verb|n| zu bewegen,
unter (eventueller) Benutzung des Turms \verb|h|.

Beispiele:
\begin{verbatim}
hanoi (1, "A", "B", "C")   => (1 von A nach B)
hanoi (2, "B", "C", "A")   => 
   (1 von B nach A)(2 von B nach C)(1 von A nach B)
hanoi (3, "A", "C", "B")   => ?
\end{verbatim}

Beachte: zum Festlegen der Schnittstelle von \verb|hanoi| \\
war schon ein Teil der Problem-Analyse nötig

\end{slide}

\begin{slide}{Türme von Hanoi: Implementierung (I)}

\begin{verbatim}
// Scheiben [ 1 .. s ] 
// von  v  nach  n  über  h
static void hanoi 
   (int s, String v, String n, String h)
\end{verbatim}
\begin{itemize}
\item
  wenn \verb|0 == s|, dann tun wir gar nichts
\item 
  wenn \verb|0 < s|, dann

  Scheibe $s$ muß wenigstens einmal bewegt werden \\
  (von $v$ nach $n$).

  Wo liegen zu diesem Zeitpunkt die anderen Scheiben?

  Wie kommen sie dorthin? von dort weg?
\end{itemize}

\end{slide}

\begin{slide}{Hanoi: Implementierung (II)}
\begin{verbatim}
static void move 
    (int s, String v, String n) {
  System.out.println 
    (s + " von " + v + " nach " + n);
}
// Testfall:  hanoi (4, "A", "B", "C");
static void hanoi 
    (int s, String v, String n, String h) 
{ if (0 < s) {
    hanoi (s - 1, v, h, n);
    move  (s, v, n);
    hanoi (s - 1, h, n, v);
} }
\end{verbatim}
\end{slide}

\begin{slide}{Hanoi: Bewertung/Aufgabe}

\begin{itemize} \itemsep 0pt
\item
  die angegebene Lösung ist optimal 

  (Grund: Scheibe $s$ muß wenigstens einmal bewegt werden,
  und sie wird nur genau einmal bewegt.)
\item
  wieviele Schritte (für $3,4,5, \dots, s$ Scheiben)
  erfordert angegebene Lösung?
\item
  Aufgabe (autotool): wie lautet die optimale Lösung
  für \emph{vier} Türme und $6, 8, 10, \dots$ Scheiben? 

  (Es sollte ja schneller gehen als für drei.)
\item
  gibt es einen einfachen \emph{iterativen} Algorithmus \\
  (wie kann man die nächste Bewegung ausrechnen, \\
  ohne ihre Vorgeschichte zu kennen)?
\end{itemize}
\end{slide}

\begin{slide}{Rekursion}

Definition: ein Unterprogramm heißt \emph{rekursiv},
wenn es sich selbst aufruft.

Beispiel: Verarbeitung von rekursiven Datenstrukturen
\begin{verbatim}
int size (Tree b) {
  if (b ist Blatt) { return 1; } 
  else { return 
    1 + size (links(b)) + size (rechts(b)); 
} }
\end{verbatim}
Beispiel (John McCarthy): Berechne \verb|f(7); f(77);| für
\begin{verbatim}
static int f (int x) {
  if (x > 100) {    return x - 10; } 
  else { return f (f (x + 11));  }
}
\end{verbatim}


\end{slide}
