\begin{slide}{rekursive Unterprogramme}

\kopf{$ $Id: rekurs.tex,v 1.2 2007-11-08 13:18:12 waldmann Exp $ $}

ein Unterprogramm kann ein anderes benutzen (aufrufen).

wenn es sogar sich selbst aufruft,
heißt es \emph{rekursiv} 

(re-current: rückläufig $\approx$ selbstbezüglich)

\begin{verbatim}
-- Vorbedingung: a und b natürliche Zahlen
Zahl up (Zahl a, Zahl b) {
    if (b > 0) {
      Rückgabe  1 + up(a, b-1);
    } else {
      Rückgabe  a;
    }
}
\end{verbatim}

\end{slide}

\begin{slide}{Rekursive Programme zum Einfügen}

\begin{verbatim}
linear-einf (Zahlenfolge a[0 .. n-1], Zahl a[n]) {
  if (n > 0) {
    if (a[n-1] > a[n]) {
      tausche (a[n-1], a[n]);
      linear-einf (a[0 .. n-2],  a[n-1]);
} } }
binär-einf (Zahlenfolge a[0..n-1], Zahl x) {
  if (n > 0) {
    Zahl i := n / 2; -- abrunden
    if (a[i] < x) { 
      binär-einf (a[i+1 .. n-1], x);
    } else {
      binär-einf (a[0   .. i-1], x);
} } }
\end{verbatim}
  


\end{slide}


