source_rekursion.src

\input{preamble}

\begin{document}
\section{Java-Stack}
\SidebarCite{book:javase15-std}
\begin{frame}[fragile]{Javas' Speicherverwaltung}
\centering\pause%
\begin{columns}[c]%
\begin{column}{.45\linewidth}%
\begin{plainjava}
!*\md4*!int x = 0;
!*\md5*!byte y = 12;
!*\md6*!String f = "Hallo Welt";
!*\md7*!char[] c = {2, 3, 4};
\end{plainjava}
\end{column} \begin{column}{.45\linewidth}
\resizebox{\linewidth}!{\begin{tikzpicture}
    \onslide<3->{\fill[lgray,rounded corners] (0,0) rectangle ++(3,5.5);
    \fill[lgray,rounded corners] (3.5,0) rectangle ++(3,5.5);
    \node[ldesc,below] at (1.5,0) {Stack};
    \node[ldesc,below] at (5,0) {Heap};
    \node[lrel] at (1.5,5) {\ldots};
    \node[lrel] at (5,5) {\ldots};
    }
    \onslide<4->{\node[lrel] at (1.5,5-.85) {\bjava{int x = 0}};}
    \onslide<5->{\node[lrel] at (1.5,5-.85*2) {\bjava{byte y = 12}};}
    \onslide<6->{
        \node[lrel] (fg) at (1.5,5-.85*3) {\bjava{String f =\ }\raisebox{-1pt}\faGenderless};
        \node[lrel] (ft) at (5,5-.85-.425) {\bjava{\"Hallo Welt\"}};
        \draw[lightgray,very thick,-Kite]  (fg.east) to[out=0,in=180] (ft.west);
    }
    \onslide<7->{
        \node[lrel] (cg) at (1.5,5-.85*4) {\bjava{char[] c =\ }\raisebox{-1pt}\faGenderless};
        \node[lrel] (ct) at (5,5-.85*4) {\bjava{\{2, 3, 4\}}};
        \draw[lightgray,very thick,-Kite]  (cg.east) -- (ct.west);
    }
\end{tikzpicture}}
\end{column}
\end{columns}
\end{frame}
\SidebarCite{gh:tikzpingus}
\begin{frame}[fragile]{Komplexere Konstrukte}
\centering\pause%
\begin{columns}[c]%
\begin{column}{.45\linewidth}%
\begin{plainjava}[morekeywords={[3]{Mega}}]
class Mega {
    public int i;
    public String s;
}

!*\md{3-4}*!Mega mon = new Mega();
!*\md5*!mon.s = "Hallo";
!*\md6*!mon.s = "Welt";
\end{plainjava}
\end{column} \begin{column}{.45\linewidth}
\resizebox{\linewidth}!{\begin{tikzpicture}
    \onslide<2->{\fill[lgray,rounded corners] (0,0) rectangle ++(3,5.5);
    \fill[lgray,rounded corners] (3.5,0) rectangle ++(3,5.5);
    \node[ldesc,below] at (1.5,0) {Stack};
    \node[ldesc,below] at (5,0) {Heap};
    \node[lrel] at (1.5,5) {\ldots};
    \node[lrel] at (5,5) {\ldots};
    }
    \onslide<3->{
        \node[lrel] (mg) at (1.5,5-.85) {\bjava[morekeywords={[3]{Mega}}]{Mega mon =\ }\raisebox{-1pt}{\faGenderless}};
        \node[lrel2] (mt) at (5,4-.85) {\bjava{int i = 0}\\[1mm]\only<3-4|handout:0>{\resizebox{25.4mm}!{\bjava{String s = null}}}\only<5->{\bjava{String s =\ }\raisebox{-1pt}{\faGenderless}}};
        \draw[lightgray,very thick,-Kite]  (mg.east) to[out=0,in=180] (mt.west);
    }
    \onslide<5->{
        \node[lrel] (st) at (5,2.75-.85) {\only<5|handout:0>{\bjava{\"Hallo\"}}\only<6->{\bjava[stringstyle={\color{gray}}]{\"Hallo\"}}};
        \only<5|handout:0>{
            \pgfinterruptboundingbox
            \draw[lightgray,very thick,-Kite] ([yshift=5mm]mt.south east) to[out=0,in=0,looseness=1.35] (st.east);
            \endpgfinterruptboundingbox
        }
    }
    \onslide<6->{
        \node[lrel] (st2) at (5,2.75-.85*2) {\bjava{\"Welt\"}};
            \pgfinterruptboundingbox
            \draw[lightgray,very thick,-Kite] ([yshift=5mm]mt.south east) to[out=0,in=0,looseness=1.25] (st2.east);
            \endpgfinterruptboundingbox
    }
\end{tikzpicture}}%
\end{column}
\end{columns}
\savebox0{\tikz{\pingu[eyes=wink, left wing wave, right wing grab,bow tie=paletteA]}}%
\begin{tikzpicture}[overlay,remember picture]
    \onslide<4->{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox0}};
        \node[left,scale=.6,text width=6.75cm,align=center,yshift=-.33cm] at (pingu.west) {Beachte: Alle Variablen erhalten in Java \say{Default-Werte}. Für komplexe Datentypen ist dies \bjava{null}.};
    }
\end{tikzpicture}%
\end{frame}
\SidebarReset

\section{Funktionsaufrufe}
\SidebarCite{book:javadoc-stack-frame}
\begin{frame}{Stack Frames}
    \vspace*{\baselineskip}
    \begin{itemize}[<+(1)->]
        \itemsep=4pt
        \item Handhaben (lokale) Gültigkeitsbereiche.
        \item Werden beim Betreten auf dem Stack abgelegt.
        \item Werden beim Verlassen wieder vom Stack entnommen.\vspace*{\medskipamount}
    \end{itemize}
\begin{center}
    \resizebox*!{2.9cm}{\begin{tikzpicture}[baseline=2.5cm+.4ex]
        \onslide<5->{
            \fill[lgray,rounded corners] (0,0) rectangle ++(3.5,5);
            \node[lrel,minimum width=33mm] (ld) at (1.75,5-.495) {\ldots};
            \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (s) at(ld.south) {%
                \T{foo}
                \nodepart{second}
                \bjava{int i = 12}\\
                \bjava{char b = 98}
            };
            \draw[ultra thick,lgray] (s.text split west) -- (s.text split east);
            \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (d) at (s.south) {%
                \T{bar}
                \nodepart{second}
                \bjava{int i = 23}
            };
            \draw[ultra thick,lgray] (d.text split west) -- (d.text split east);
        }
    \end{tikzpicture}\onslide<6->{\quad$\Longrightarrow$\quad
    \begin{tikzpicture}[baseline=2.5cm+.4ex]
            \fill[lgray,rounded corners] (0,0) rectangle ++(3.5,5);
            \node[lrel,minimum width=33mm] (ld) at (1.75,5-.495) {\ldots};
            \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (s) at(ld.south) {%
                \T{foo}
                \nodepart{second}
                \bjava{int i = 12}\\
                \bjava{char b = 98}
            };
            \draw[ultra thick,lgray] (s.text split west) -- (s.text split east);
        \node[below=1mm,ldesc] at(current bounding box.south) {\Large\strut Verlasse bar};
    \end{tikzpicture}}\onslide<7->{\quad$\Longrightarrow$\quad
    \begin{tikzpicture}[baseline=2.5cm+.4ex]
            \fill[lgray,rounded corners] (0,0) rectangle ++(3.5,5);
            \node[lrel,minimum width=33mm] (ld) at (1.75,5-.495) {\ldots};
            \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (s) at(ld.south) {%
                \T{foo}
                \nodepart{second}
                \bjava{int i = 12}\\
                \bjava{char b = 98}
            };
            \draw[ultra thick,lgray] (s.text split west) -- (s.text split east);
            \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (d) at (s.south) {%
                \T{far}
                \nodepart{second}
                \bjava{char c = 'm'}
            };
            \draw[ultra thick,lgray] (d.text split west) -- (d.text split east);
            \node[below=1mm,ldesc] at(current bounding box.south) {\Large\strut Betrete far};
    \end{tikzpicture}}\onslide<8->{\quad$\Longrightarrow$\quad
    \begin{tikzpicture}[baseline=2.5cm+.4ex]
            \fill[lgray,rounded corners] (0,0) rectangle ++(3.5,5);
            \node[lrel,minimum width=33mm] (ld) at (1.75,5-.495) {\ldots};
            \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (s) at(ld.south) {%
                \T{foo}
                \nodepart{second}
                \bjava{int i = 12}\\
                \bjava{char b = 98}
            };
            \draw[ultra thick,lgray] (s.text split west) -- (s.text split east);
            \node[below=1mm,ldesc] at(current bounding box.south) {\Large\strut Verlasse far};
    \end{tikzpicture}}\onslide<9->{\quad$\Longrightarrow$\quad
    \begin{tikzpicture}[baseline=2.5cm+.4ex]
            \fill[lgray,rounded corners] (0,0) rectangle ++(3.5,5);
            \node[lrel,minimum width=33mm] at (1.75,5-.495) {\ldots};
            \node[below=1mm,ldesc] at(current bounding box.south) {\Large\strut Verlasse foo};
    \end{tikzpicture}}}
\end{center}
\end{frame}

\savebox\pinguA{\tikz{\pingu[wings hug,eyes wink,hairs=paletteA!80!white,hair 3=paletteA]}}%
\savebox\pinguB{\tikz{\pingu[glasses round, left wing shock, eyes shock, right wing grab,tie=paletteB]}}%
\savebox\pinguC{\tikz{\pingu[wings wave,right eye wink,halo,small]}}%
\begin{frame}[fragile]{Stack Frames -- Beispiel}
\centering\pause\vspace*{-1.75em}% space fine tuning
\begin{columns}[c]%
\begin{column}{.5\linewidth}%
\begin{plainjava}[escapeinside={!}{!}]
!\md{11}!void f(char c) {
!\md{12}!  int x = 4;
!\md*{5}{17}!  System.out.print(!\mb{13}!b(c+x)!\mh{16}!);!\mh{18}!
}
!\md*{2,4}{5,14}!String b(int n) {
!\md{6-7,15}!  return "" + (n % 9);
}

!\md{10}!f(!\mb4!b(42)!\rlap{\!\mb{8}}!.!\rlap{~~\thinspace\mb[3]{9}}!charAt(0));!\mh[6]{19}!
\end{plainjava}
\end{column} \begin{column}{.415\linewidth}
\centering\resizebox{\linewidth}!{\begin{tikzpicture}
    \onslide<3->{\fill[lgray,rounded corners] (0,0) rectangle ++(3,5.5);
    \node[ldesc,below] at (1.5,0) {Stack};
    \node[lrel] (d) at (1.5,5) {\ldots};
    \fill[lgray,rounded corners] (3.5,0) rectangle ++(3,5.5);
    \node[ldesc,below] at (5,0) {Heap};
    \node[lrel] (d2) at (5,5) {\ldots};}
    \onslide<5-7|handout:2>{\node[lsf,below=1mm] (s) at(d.south) {%
        \T{b}
        \nodepart{second}
        \bjava{int n = 42}%
    };
    \draw[ultra thick,lgray] (s.text split west) -- (s.text split east);
    }
    \onslide<8-9|handout:3>{%
        \node[lrel,below=1mm] (br) at (d.south) {\bjava{<ret-b> =\ }\raisebox{-1pt}\faGenderless};
        \node[lrel,below=8mm] (br2) at (d2.south) {\bjava{\"6\"}};
        \draw[lightgray,very thick,-Kite]  (br.east) to[out=0,in=180] (br2.west);
    }
    \onslide<10-|handout:4->{
        \node[lrel,below=8mm] (br2) at (d2.south) {\bjava[stringstyle={\color{gray}}]{\"6\"}};
    }
    \onslide<9|handout:3>{%
        \node[lsf,below=1mm] (ca) at (br.south) {\resizebox{25.4mm}!{\textit{\color{gray}\bjava{String::charAt}}}\nodepart{second} \scriptsize\textit{omitted}};
        \draw[ultra thick,lgray] (ca.text split west) -- (ca.text split east);
        \draw[lightgray,very thick,-Kite]  ([yshift=-3.5mm]ca.east) to[out=0,in=180] (br2.west);
    }
    \onslide<10|handout:0>{%
        \node[lrel,below=1mm] (rca) at (d.south) {\resizebox{25.4mm}!{\bjava{<ret-cA> = '6'}}};
    }
    \onslide<11|handout:0>{%
        \node[lsf,below=1mm] (fs) at (d.south) {%
            \T{f}
            \nodepart{second}
            \bjava{char c = '6'}%
        };
        \draw[ultra thick,lgray] (fs.text split west) -- (fs.text split east);
    }
    \onslide<12-18|handout:4-5>{%
        \node[lsf,below=1mm] (fs) at (d.south) {%
            \T{f}
            \nodepart{second}
            \bjava{char c = '6'}\\
            \bjava{int x = 4}%
        };
        \draw[ultra thick,lgray] (fs.text split west) -- (fs.text split east);
    }
    \onslide<14-15|handout:4>{%
        \node[lsf,below=1mm] (bs) at (fs.south) {%
            \T{b}
            \nodepart{second}
            \bjava{char n = 58}
        };
        \draw[ultra thick,lgray] (bs.text split west) -- (bs.text split east);
        \node[above=1mm,scale=.65] (pingu2) at (5,0) {\usebox\pinguA};
        \node[above=2mm,lrel,draw=gray,minimum width=0mm,minimum height=0mm] at(pingu2.south) {\bjava{'6' = 54}};
    }
    \onslide<16|handout:0>{%
        \node[lrel,below=1mm] (rbs) at (fs.south) {\resizebox{25.4mm}!{\bjava{<ret-b> =\ }\raisebox{-1pt}\faGenderless}};
        \node[lrel,below=11mm] (br3) at (br2.south) {\bjava{\"4\"}};
        \draw[lightgray,very thick,-Kite]  (rbs.east) to[out=-15,in=165] (br3.west);
    }
    \onslide<17|handout:5>{\node[lrel,below=11mm] (br3) at (br2.south) {\bjava{\"4\"}};}
    \onslide<18-|handout:6->{%
        \node[lrel,below=11mm] (br3) at (br2.south) {\bjava[stringstyle={\color{gray}}]{\"4\"}};
    }
    \onslide<17|handout:5>{%
        \node[lsf,below=1mm] (print) at (fs.south) {\resizebox{25.4mm}!{\textit{\color{gray}\bjava{PrintStream::print}}}\nodepart{second} \scriptsize\textit{omitted}};
        \draw[ultra thick,lgray] (print.text split west) -- (print.text split east);
        \draw[lightgray,very thick,-Kite]  ([yshift=-2.5mm]print.east) to[out=-15,in=165] (br3.west);
    }
    \onslide<19-|handout:6->{%
        \node[above=1mm,scale=.65] (pingu3) at (1.5,0) {\usebox\pinguC};
        \node[above=1mm,lrel,draw=gray,text width=25.3mm,minimum height=0mm,font=\sffamily\tiny] at(pingu3.north) {Die grauen Zeichenketten auf dem Heap können bereits vom Garbage-Collector entfernt worden sein!};
    }
\end{tikzpicture}}%
\vspace*{-1.25em}%
\end{column}
\end{columns}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<7-|handout:2->{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguB}};
        \node[left,scale=.6,text width=6.75cm,align=center,yshift=-.33cm] at (pingu.west) {Wir werden Rückgabemechanismen sträflich vereinfachen!};
    }
\end{tikzpicture}%
\end{frame}
\SidebarReset

\section{Theoretisches}
\subsection{Der Grundriss einer Rekursion}
\savebox\pinguA{\tikz{\pingu[eyes wink, wings wave, eye patch left, eye patch right,belly=\Large\faStar,lightsaber left=paletteB!81!white,lightsaber left outer glow factor=.0615,left item angle=42,pants=pingu@bronze,pants bands]}}%
\begin{frame}{Anatomie einer Rekursion}
\begin{columns}[c]
\begin{column}{.6\linewidth}\linespread{1.5}\scriptsize%
\SetKwProg{Fn}{func}{ is}{end}%
\begin{algorithm}[H]
\PreCode\StartCode
\onslide<2->{\Fn{recursive(problem arguments)}{%
    \onslide<3->{\uIf{at elemental problem}{
            \onslide<4->{
                solve elemental problem\;
            }
        }
        \Else{%
            \onslide<5->{Split problem into smaller ones\;}
            \onslide<6->{Try to solve them recursively\;}
            \onslide<7->{Combine step-solutions to one\;}
        }
    }
}}
\end{algorithm}
\end{column} \begin{column}{.35\linewidth}
\centering\onslide<8->{\begin{tikzpicture}
    \node[scale=.6] (pingu) at(0,0) {\usebox\pinguA};
    \node[below=1mm,scale=.6,align=center,text width=5cm] at(pingu.south) {%
        Nicht alle müssen genau dieser Struktur folgen.\\[.5ex] Be special. Be wild!%
    };
\end{tikzpicture}}
\end{column}
\end{columns}
\end{frame}

\begin{frame}[fragile]{Stack Frames und Aufrufgraphen}
    \begin{itemize}[<+(1)->]
        \itemsep10pt
        \item Stack Frames werden schnell unübersichtlich.
        \item Wir vereinfachen dies durch Aufrufgraphen.
        \item Knoten repräsentieren Stack Frames.\bigskip
    \end{itemize}
\begin{columns}[c]
    \begin{column}{.325\linewidth}\lstfs{9}%
\begin{plainjava}
!*\onslide<5->*!int f(int x) {
!*\onslide<5->*!    return f(x - 1);
!*\onslide<5->*!}
\end{plainjava}
    \end{column} \begin{column}{.2\linewidth}
\centering
\onslide<6->{\resizebox{.775\linewidth}!{\begin{tikzpicture}
    \fill[lgray,rounded corners] (0,-.5) rectangle ++(3.5,5.5);
    \node[lrel,minimum width=33mm] (ld) at (1.75,5-.495) {\ldots};
    \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (s) at(ld.south) {%
        \T{f}
        \nodepart{second}
        \bjava{int x = 3}
    };
    \draw[ultra thick,lgray] (s.text split west) -- (s.text split east);
    \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (d) at (s.south) {%
        \T{f}
        \nodepart{second}
        \bjava{int x = 2}
    };
    \draw[ultra thick,lgray] (d.text split west) -- (d.text split east);
    \node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (f3) at (d.south) {%
    \T{f}
    \nodepart{second}
    \bjava{int x = 1}
};
\draw[ultra thick,lgray] (f3.text split west) -- (f3.text split east);
\end{tikzpicture}}}
    \end{column} \begin{column}{.3\linewidth}
\onslide<7->{%
\scalebox{0.9}{\begin{tikzpicture}
    \node[lblob,scale=.75] (0) at(0,0) {\color{black}\T{f(3)}};
    \node[lblob,scale=.75] (1) at(1,-1) {\color{black}\T{f(2)}};
    \node[lblob,scale=.75] (2) at(2,-2) {\color{black}\T{f(1)}};
    \draw[lgray,thick,-Kite] (0) -- (1);
    \draw[lgray,thick,-Kite] (1) -- (2);
\end{tikzpicture}}}
    \end{column}
\end{columns}
\end{frame}

\subsection{Rekursionsvarianten}
\SidebarCite{dive:recursion}
\savebox\pinguB{\tikz{\pingu[glasses, left wing wave, eyes angry, right wing grab,silver medal,medal band=paletteA,hat,lollipop left=paletteA]}}%
\savebox\pinguC{\tikz{\pingu[right wing wave,cane left=brown!80!paletteA!70!black,hand cast right=\paletteA{\faExclamation},tie=paletteC,eyes wink,hair=paletteC]}}
\subsubsection{Lineare Rekursion}
\begin{frame}[fragile]{Lineare Rekursion}
    \pause\begin{columns}[c]
        \begin{column}{.525\linewidth}\lstfs{8}
\begin{plainjava}[escapeinside={!}{!}]
!\md{2}!int f(int n) {
!\md{6}!  if (n <= 0) return n;
!\md{3}!  else return n + !\mb{4-5}!f(n - 1);!\mh{7-10}!
}
\end{plainjava}
        \end{column} \begin{column}{.425\linewidth}
\begin{tikzpicture}
\foreach[remember=\i as \li (initially 0)] \i/\mi/\ri/\xc in {1/3/9/3,2/4/9/3,3/5/8/1,4/6/7/0} {
    \onslide<\mi->{%
        \node[lblob,scale=.825] (l\i) at (\i,-\i/3) {\color{black}\resizebox{4.75mm}!{\T{f(\the\numexpr4-\i)}}};
        \ifnum\li>0 \draw[lgray,thick,Kite-] (l\i) -- (l\li); \fi
    }
    \onslide<\ri->{%
        \ifnum\li>0 \draw[lgray,thick,Kite-] (l\li.60) to[bend left,edge node={node[above right,text=gray] {\footnotesize\xc}}] (l\i.110); \fi
    }
}
\onslide<10->{
    \node[above left=1.5mm,gray] at (l1) {\footnotesize 6};
}
\end{tikzpicture}
        \end{column}
    \end{columns}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<11->{\node[above=12mm,scale=.6] (pingu) at(current page.south) {\usebox\pinguC};
        \node[below right=2mm,align=left,scale=.6,text width=7cm] at(pingu.north east) {%
            Die einfachste und geläufigste Form der Rekursion.\medskip\\
            Hier handelt es sich sogar um eine \textit{primitiv-rekursive} Funktion!\textsuperscript{\cite{dive:recursion}}%
        };
    }
    \onslide<12->{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguB}};
        \node[left,scale=.6,text width=7.25cm,align=center,yshift=-.33cm] at (pingu.west) {Lineare Rekursion wird weiter unterteilt! So beispielweise in Head- und Tailrekursiv.};
    }
\end{tikzpicture}
\end{frame}
\SidebarReset

\savebox\pinguA{\tikz{\pingu[left wing wave,glasses,left eye wink,pants=paletteA]}}
\savebox\pinguB{\tikz{\pingu[eyes wink, crown, crown 3d,wings raise]}}
\savebox\pinguC{\tikz{\pingu[left wing wave,glasses,left eye wink,right wing shock, eyes shock,pants=paletteA]}}
\SidebarCite{dive:ackermann}
\subsubsection{Verschachtelte Rekursion}
\begin{frame}[fragile]{Verschachtelte Rekursion}
    \pause\begin{columns}[c]
        \begin{column}{.575\linewidth}\lstfs{8}
\begin{plainjava}[escapeinside={!}{!},moredelim={**[is][{\only<2|handout:0>{\solhlboxd{fill=shadeA}}}]{|mark|}{|mark|}}]
int a(int m, int n) {
!\md{6-7,11}!  if(m == 0) return n + 1;
!\md{5}!  else if (n == 0) return a(m - 1, 1);!\mh{8}!
!\md{3}!  else return !\mb[1]{10}!a(m - 1, !\mb{4}!|mark|a(m, n - 1)|mark|!\mh{9}!);
}
\end{plainjava}
        \end{column} \begin{column}{.375\linewidth}
\begin{tikzpicture}[lblock/.append style={text=black,scale=.8},baseline=-3cm]
\onslide<3-|handout:1->{\node[lblock] (l1) at (0,0) {\T{a(1, 1)}};}
\onslide<4-|handout:1->{\node[lblock] (l2) at (0,-1) {\T{a(1, 0)}}; \draw[lgray,thick,-Kite] (l1) -- (l2);}
\onslide<6-|handout:1->{\node[lblock] (l3) at (0,-2) {\T{a(0, 1)}}; \draw[lgray,thick,-Kite] (l2) -- (l3);}
\onslide<7-|handout:1->{\node[right,gray,scale=.65] at(l3.east) {2};}
\onslide<8-|handout:1->{\draw[lgray,thick,-Kite] (l3.west) to[bend left=40] (l2.west); \node[right,gray,scale=.65] at(l2.east) {2};}
\onslide<9-|handout:1->{\draw[lgray,thick,-Kite] (l2.west) to[bend left=40] (l1.west);}
\onslide<10-|handout:1->{\node[lblock] (l4) at (2,0) {\T{a(0, 2)}};
\draw[lgray,thick,-Kite] (l1.east) -- (l4.west);}
\onslide<11-|handout:2->{\node[right,gray,scale=.65] at(l4.east) {3};}
\onslide<12-|handout:2->{\draw[lgray,thick,-Kite] (l4.north) to[bend right=32] (l1.north);}
\end{tikzpicture}
        \end{column}
    \end{columns}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<2->{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguB}};
        \node[left,scale=.6,gray,xshift=.5cm,text width=6.33cm,align=center,yshift=-.33cm] at (pingu.west) {Dies ist die Ackermann Funktion!};
    }
    \onslide<13-|handout:2->{%
        \node[above right,yshift=12mm,scale=.6,text width=30mm,align=right] (pingu2) at(current page.south) {\only<13-14|handout:0>{\usebox\pinguA}\only<15-|handout:2->{\usebox\pinguC}};
        \node[below right=1mm,yshift=-5mm,align=left,scale=.6,text width=7cm] at(pingu2.north east) {%
            Damit ist \(a(1, 1) = 3\).\medskip\\
            \only<14->{Was ist dann beispielsweise \(a(4, 2)\)?\smallskip\\}
            \only<15->{Nun\ldots\ \(a(4, 2) \approx 2 \cdot 10^{19\,729}\).}
        };
    }
    \onslide<16-|handout:2->{%
        \node[below left=1mm,yshift=-5mm,align=right,scale=.6,text width=7cm] at(pingu2.north west) {%
            Verschachtelt-Rekursive Funktionen sind meist sehr schwer nachzuvollziehen.
        };
    }
\end{tikzpicture}
\end{frame}
\SidebarReset

\savebox\pinguA{\tikz{\pingu[crown 2d=pingu@bronze, wings grab, cup=paletteA, right eye wink,crown gem colors={paletteA!70!white}{paletteB!70!white}{paletteC!70!white}{paletteD!50!white}{paletteC!70!white}{paletteB!70!white}{paletteA!70!white}]}}%
\savebox\pinguB{\tikz{\pingu[sunglasses, eyes wink, right wing grab, bow tie=paletteA,hairs=paletteD]}}%
\subsubsection{Kaskadenförmige Rekursion}
\SidebarCite{dive:fibonacci}
\begin{frame}[fragile]{Kaskadenförmige Rekursion}
    \pause\begin{columns}[c]
        \begin{column}{.5\linewidth}\lstfs{8}
\begin{plainjava}[escapeinside={!}{!}]
!\md{3}!int f(int n) {
!\md{7,9,12,16,18}!    if(n <= 2) return 1;
    else return !\mb{4-6,14-15}!f(n - 1) + !\mb[1]{8,11,13,17}!f(n - 2);!\mh{10,19-20}!
}
\end{plainjava}
        \end{column} \begin{column}{.425\linewidth}
\resizebox{\linewidth}!{\begin{tikzpicture}[lblob/.append style={text=black,scale=.8},xscale=1.33]
    \onslide<3-|handout:1->{\node[lblob] (0) at(0,0) {\T{f(5)}};}
    \onslide<4-|handout:1->{\node[lblob] (1) at(-1.5,-1.5) {\T{f(4)}}; \draw[lgray,thick,-Kite] (0) -- (1);}
    \onslide<13-|handout:2->{\node[gray,above left] at(1.north west) {3}; \draw[lgray,thick,-Kite] (1) to[bend left=30] (0);}
    \onslide<14-|handout:2->{\node[lblob] (2) at(1.5,-1.5) {\T{f(3)}}; \draw[lgray,thick,-Kite] (0) -- (2);}

    \onslide<5-|handout:1->{\node[lblob] (3) at(-2.5,-3) {\T{f(3)}}; \draw[lgray,thick,-Kite] (1) -- (3);}
    \onslide<11-|handout:2->{\node[lblob] (4) at(-.5,-3) {\T{f(2)}}; \draw[lgray,thick,-Kite] (1) -- (4);}
    \onslide<12-|handout:2->{\node[gray,below] at(4.south) {1}; \draw[lgray,thick,-Kite] (4) to[bend right=30] (1);}
    \onslide<15-|handout:2->{\node[lblob] (5) at(.5,-3) {\T{f(2)}}; \draw[lgray,thick,-Kite] (2) -- (5);}
    \onslide<16-|handout:2->{\node[gray,below] at(5.south) {1}; \draw[lgray,thick,-Kite] (5) to[bend left=30] (2);}
    \onslide<17-|handout:2->{\node[lblob] (6) at(2.5,-3) {\T{f(1)}}; \draw[lgray,thick,-Kite] (2) -- (6);}
    \onslide<18-|handout:2->{\node[gray,below] at(6.south) {1}; \draw[lgray,thick,-Kite] (6) to[bend right=30] (2);}
    \onslide<19-|handout:2->{\node[gray,above right] at(2.north east) {2}; \draw[lgray,thick,-Kite] (2) to[bend right=30] (0);}
    \onslide<20-|handout:2->{\node[gray,above] at(0.north) {5};}

    \onslide<6-|handout:1->{\node[lblob] (7) at(-3,-4.5) {\T{f(2)}}; \draw[lgray,thick,-Kite] (3) -- (7);}
    \onslide<7-|handout:1->{\node[gray,below] at(7.south) {1}; \draw[lgray,thick,-Kite] (7) to[bend left=30] (3);}
    \onslide<8-|handout:2->{\node[lblob] (8) at(-2,-4.5) {\T{f(1)}};  \draw[lgray,thick,-Kite] (3) -- (8);}
    \onslide<9-|handout:2->{\node[gray,below] at(8.south) {1}; \draw[lgray,thick,-Kite] (8) to[bend right=30] (3);}
    \onslide<10-|handout:2->{\node[gray,above left] at(3.north west) {2}; \draw[lgray,thick,-Kite] (3) to[bend left=30] (1);}
\end{tikzpicture}}
        \end{column}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<21-|handout:2>{%
        \node[above=.25cm,yshift=1cm,scale=.6] (pingu) at (current page.south) {\usebox\pinguA};
        \node[left,scale=.6,text width=6.33cm,align=center,yshift=-.33cm] at (pingu.west) {Elegant, aber meist nicht sonderlich effizient.};
    }
    \onslide<22-|handout:2>{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguB}};
        \node[left=-2mm,scale=.6,text width=6.75cm,gray,xshift=.15cm,align=center,yshift=-.33cm] at (pingu.west) {Sie wird manchmal auch \say{verzweigte Rekursion} genannt.};
    }
\end{tikzpicture}
    \end{columns}
\end{frame}
\SidebarReset

\savebox\pinguB{\tikz{\pingu[eyes wink, right wing grab,eye patch left,belly=\Large\faHeart]}}%
\subsubsection{Wechselseitige Rekursion}
\begin{frame}[fragile]{Wechselseitige Rekursion}
    \pause\begin{columns}[c]
        \begin{column}{.5\linewidth}\lstfs{8}
\begin{plainjava}[escapeinside={!}{!}]
!\md{3}!int a(int x) {
    if(x <= 0) return x + 1;
    return !\mb{4,6,8}!b(x - 1);!\mh[2]{11,13,15}!
}

int b(int x) {
!\md*{1}{9}!    if(x <= 0) return !\mb{10}!x;
!\md{5}!    return !\mb{7}!a(x % 3);!\mh{12,14}!
}
\end{plainjava}
        \end{column} \begin{column}{.425\linewidth}
\centering\resizebox{.625\linewidth}!{\begin{tikzpicture}[lblob/.append style={text=black,scale=.8},xscale=1.33]
    \onslide<3->{\node[lblob] (0) at(0,0) {\T{a(42)}};}
    \onslide<4->{\node[lblob] (1) at(2,-.75) {\T{b(41)}}; \draw[lgray,thick,-Kite] (0) -- (1);}
    \onslide<6-|handout:1->{\node[lblob] (2) at(0,-1.5) {\T{a(2)}}; \draw[lgray,thick,-Kite] (1) -- (2);}
    \onslide<7-|handout:1->{\node[lblob] (3) at(2,-2.25) {\T{b(1)}}; \draw[lgray,thick,-Kite] (2) -- (3);}
    \onslide<8-|handout:1->{\node[lblob] (4) at(0,-3) {\T{a(1)}}; \draw[lgray,thick,-Kite] (3) -- (4);}
    \onslide<9-|handout:1->{\node[lblob] (5) at(2,-3.75) {\T{b(0)}}; \draw[lgray,thick,-Kite] (4) -- (5);}
    \onslide<10-|handout:2->{\node[gray,right=1mm,scale=.9] at (5.east) {0};}
    \onslide<11-|handout:2->{\node[gray,left=1mm,scale=.9] at (4.west) {0}; \draw[lgray,thick,-Kite] (5) to[bend right=20] (4);}
    \onslide<12-|handout:2->{\node[gray,right=1mm,scale=.9] at (3.east) {0}; \draw[lgray,thick,-Kite] (4) to[bend left=20] (3);}
    \onslide<13-|handout:2->{\node[gray,left=1mm,scale=.9] at (2.west) {0}; \draw[lgray,thick,-Kite] (3) to[bend right=20] (2);}
    \onslide<14-|handout:2->{\node[gray,right=1mm,scale=.9] at (1.east) {0}; \draw[lgray,thick,-Kite] (2) to[bend left=20] (1);}
    \onslide<15-|handout:2->{\node[gray,left=1mm,scale=.9] at (0.west) {0}; \draw[lgray,thick,-Kite] (1) to[bend right=20] (0);}
\end{tikzpicture}}
        \end{column}
    \end{columns}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<3-|handout:1->{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguB}};
        \node[left=-2mm,scale=.6,text width=6.75cm,align=center,yshift=-.33cm] at (pingu.west) {Sie kann durch Funktionstupel stets in \say{normale} Rekursionen transformiert werden.};
    }
\end{tikzpicture}%
\end{frame}

\SidebarCite{dive:recursionvsit}
\begin{frame}{Ein paar Notizen}
\begin{itemize}[<+(1)->]
    \itemsep13pt
    \item Die gezeigten Beispiele waren möglichst minimal
    \item Die Varianten können kombiniert werden!\pause{}\smallskip\par
        \faAngleRight\ z.B. eine kaskadenförmige, wechselseitige Rekursion.
    \item Rekursion und Iteration sind meist gleich mächtig.
\end{itemize}
\end{frame}
\SidebarReset

\subsection{Head- vs. Tail-Rekursion}
\savebox\pinguA{\tikz{\pingu[right wing grab, sun glasses round=brown!65!black,eyes shiny]}}%
\savebox\pinguB{\tikz{\pingu[wings shock, sun glasses round=brown!65!black, eyes angry,devil horns=paletteA]}}%
\begin{frame}[fragile]{Head- vs. Tail-Rekursion}
\pause\lstfs{8}\begin{columns}[c]
        \begin{column}{.425\linewidth}
\centering
\begin{plainjava}[escapeinside={!}{!}]
!\md{3}!void h(int n) {
!\md{7}!    if(n <= 0) return;
!\md{4-6}!    h(n - 1);
!\md{8,10,12}!    System.out.println(n);!\mh[1]{9,11,13-14}!
}
\end{plainjava}
\resizebox{.8\linewidth}!{\begin{tikzpicture}[lblob/.append style={text=black,scale=.8},xscale=1.33]
    \onslide<3->{\node[lblob] (3) at(0,0) {h(3)};}
    \onslide<5->{\node[lblob] (2) at(1,0) {h(2)}; \draw[lgray,thick,-Kite] (3) -- (2);}
    \onslide<6->{\node[lblob] (1) at(2,0) {h(1)}; \draw[lgray,thick,-Kite] (2) -- (1);}
    \onslide<7->{\node[lblob] (0) at(3,0) {h(0)}; \draw[lgray,thick,-Kite] (1) -- (0);}
    \onslide<8-|handout:1>{\draw[lgray,thick,-Kite] (0.110) to[bend right] (1.70);}
    \onslide<9-|handout:1>{\node[below,gray,scale=.8] at(1.south) {1};}
    \onslide<10-|handout:1>{\draw[lgray,thick,-Kite] (1.110) to[bend right] (2.70);}
    \onslide<11-|handout:1>{\node[below,gray,scale=.8] at(2.south) {2};}
    \onslide<12-|handout:1>{\draw[lgray,thick,-Kite] (2.110) to[bend right] (3.70);}
    \onslide<13-|handout:1>{\node[below,gray,scale=.8] at(3.south) {3};}

    \onslide<14-|handout:1>{
        \node[below=5mm] at(current bounding box.south) {Ausgabe:  \T{1} \(\to\) \T{2} \(\to\) \T{3}};
    }
\end{tikzpicture}}
        \end{column} \begin{column}{.425\linewidth}
\centering
\begin{plainjava}[escapeinside={!}{!}]
!\md{3}!void t(int n) {
!\md{10}!    if(n <= 0) return;
!\md{4-5,7,9}!    System.out.println(n);
    !\mb{6,8}!t(n - 1);!\mh[1]{11-14}!
}
\end{plainjava}
\resizebox{.8\linewidth}!{\begin{tikzpicture}[lblob/.append style={text=black,scale=.8},xscale=1.33]
    \onslide<3->{\node[lblob] (3) at(0,0) {t(3)};}
    \onslide<5->{\node[below,gray,scale=.8] at(3.south) {3};}
    \onslide<6->{\node[lblob] (2) at(1,0) {t(2)}; \draw[lgray,thick,-Kite] (3) -- (2);}
    \onslide<7->{\node[below,gray,scale=.8] at(2.south) {2};}
    \onslide<8->{\node[lblob] (1) at(2,0) {t(1)}; \draw[lgray,thick,-Kite] (2) -- (1);}
    \onslide<9->{\node[below,gray,scale=.8] at(1.south) {1};}
    \onslide<10->{\node[lblob] (0) at(3,0) {t(0)}; \draw[lgray,thick,-Kite] (1) -- (0);}
    \onslide<11-|handout:1>{\draw[lgray,thick,-Kite] (0.110) to[bend right] (1.70);}
    \onslide<12-|handout:1>{\draw[lgray,thick,-Kite] (1.110) to[bend right] (2.70);}
    \onslide<13-|handout:1>{\draw[lgray,thick,-Kite] (2.110) to[bend right] (3.70);}
    \onslide<14-|handout:1>{
        \node[below=5mm] at(current bounding box.south) {Ausgabe: \T{3} \(\to\) \T{2} \(\to\) \T{1}};
    }
\end{tikzpicture}}
        \end{column}
    \end{columns}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<15-|handout:1>{%
        \node[below left=.25cm,yshift=.8cm,scale=.6] (pingu) at (current page.north east) {\rotatebox[origin=c]{180}{\usebox\pinguA}};
        \node[left,scale=.6,text width=6.75cm,align=center,yshift=-.33cm] at (pingu.west) {Kurzgesagt: Passiert noch etwas im rekursiven Aufstieg oder nicht (tail).};
    }
    \onslide<16-|handout:1>{%
        \node[above right=-.66cm,scale=.6] (pingu) at (current page.south west) {\rotatebox[origin=c]{-45}{\usebox\pinguB}};
        \node[above=1.5mm,scale=.5,gray,text width=5.5cm,align=center,yshift=-.33cm] at (pingu.north east) {Disclaimer: Die Feinheiten einer Head-Rekursion werden hier vernachlässigt. Tail-Rekursionen sind interessanter, da sie sich problemlos in Iterationen transformieren lassen.};
    }
\end{tikzpicture}%
\end{frame}

\section{Beispiele}
\subsection{Mathematische Funktionen}
\subsubsection{Fakultätsfunktion}
\savebox\pinguA{\tikz{\pingu[right eye wink,sign post left={\textbf{Note!}},right wing shock,left wing hug]}}%
\begin{frame}[fragile]{Mathematische Funktionen}
\begin{itemize}[<+(1)->]
    \itemsep4pt
    \item Einige mathematischen Funktionen sind rekursiv definiert.
    \item Die gegebene Definition lässt sich meist 1:1 übersetzen.
    \item Sie nimmt bereits einiges des Denkaufwands ab.
\end{itemize}
\begin{columns}[c]
\begin{column}{.425\linewidth}
\footnotesize\onslide<5->{\begin{align*}
    f(n) &= \begin{cases}
        1,\quad & n \leq 1 \\
        n \cdot \only<5|handout:1>{\text{\hspace*{-2pt}\tikz[baseline=-.45ex]{\node[fill=shadeA,rounded corners=2pt,outer sep=0pt,inner xsep=0pt,inner ysep=1.5pt] {\hspace*{2pt}$f(n - 1)$\hspace*{2pt}};}\hspace*{-2pt}}}\only<6-|handout:0>{f(n - 1)},\quad & n > 1
    \end{cases}\\[1ex]
    \color{gray}f_n &\color{gray}:~ \N \to \N, n \mapsto n \cdot \only<5|handout:1>{\text{\hspace*{-2pt}\tikz[baseline=-.45ex]{\node[fill=shadeA!40!white,rounded corners=2pt,outer sep=0pt,inner xsep=0pt,inner ysep=1pt] {\hspace*{2pt}$f_{n - 1}$\hspace*{2pt}};}\hspace*{-2pt}}}\only<6-|handout:0>{f_{n - 1}} \\
        & \color{gray}f_1 = 1
\end{align*}}
\end{column} \begin{column}{.475\linewidth}\lstfs{9}
\begin{plainjava}
!*\onslide<6->*!public int f(int n) {
!*\onslide<7->*!  if(n <= 1) return 1;
!*\onslide<8->*!  else return n * f(n - 1);
!*\onslide<6->*!}
\end{plainjava}
\vspace*{1.5em}
\end{column}
\end{columns}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<9->{%
        \node[above right=.25cm,yshift=1cm,scale=.6] (pingu) at (current page.south west) {\usebox\pinguA};
        \node[above=1mm,scale=.6,text width=4.5cm,align=center,font=\footnotesize\sffamily] at(pingu.north) {%
            \say{Elementarprobleme} sind hier die nicht-rekursiven Fälle: Teile der Folge, welche oft axiomatisch gegeben sind.%
        };
    }
\end{tikzpicture}
\end{frame}

\subsubsection{Ackermann Funktion}
\savebox\pinguA{\tikz{\pingu[wings wave, straw hat,belly=\Large\faCode,sunglasses, glasses opacity=.9]}}%
\savebox\pinguB{\lstfs{8}%
\begin{minipage}{5cm}
\begin{plainjava}^^J
int f(int n) \{^^J
{} {} {} {}return phi(n, n, n);^^J
\}^^J
^^J
int alpha(int a, int n) \{^^J
{} {} {} {}return n <= 1 ? n : a;^^J
\}^^J
\end{plainjava}
\end{minipage}}
\begin{frame}{Die Ackermann Funktion, Alternativ\hfill \textcolor{shadeA}{\textbf{I}}}
\centering\begin{align*}
    \onslide<2->{f(n) &= \phi(n, n, n)}\\[1ex]
    \onslide<3->{\phi(a, b, 0) &= a + b }\\
    \onslide<3->{\phi(a, 0, n) &= \alpha(a, n - 1)} \\
    \onslide<3->{\phi(a, b, n) &= \phi(a, \phi(a, b - 1, n), n - 1)} \\[1ex]
    \onslide<4->{\alpha(a, n) &= \begin{cases}
        0, \quad &\text{ wenn } n = 0 \\
        1, \quad &\text{ wenn } n = 1 \\
        a, \quad &\text{ wenn } n > 1
    \end{cases}}
\end{align*}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<5->{%
        \node[above right=.25cm,yshift=1cm,scale=.6] (pingu) at (current page.south west) {\usebox\pinguA};
        \node[above=1mm,xshift=.85cm,scale=.75,text width=4.5cm,align=left,font=\footnotesize\sffamily] at(pingu.north) {\usebox\pinguB};
    }
\end{tikzpicture}
\end{frame}

\begin{frame}[c,fragile]{Die Ackermann Funktion, Alternativ\hfill \textcolor{shadeA}{\textbf{II}}}
\centering
\begin{plainjava}
!*\onslide<2->*!int phi(int a, int b, int n) {
!*\onslide<4->*!    if(n == 0) return a + b;
!*\onslide<5->*!    else if (b == 0) return alpha(a, n - 1);
!*\onslide<6->*!    else return phi(a, phi(a, b - 1, n), n - 1);
!*\onslide<2->*!}
\end{plainjava}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<3-|handout:0>{\node[above left=.5cm,yshift=1,font=\scriptsize\sffamily,gray,xshift=-.33cm,text width=5cm] at(current page.south east) {\begin{align*}
        \phi(a, b, 0) &= a + b \\
        \phi(a, 0, n) &= \alpha(a, n - 1) \\
        \phi(a, b, n) &= \phi(a, \phi(a, b - 1, n), n - 1)
    \end{align*}};}

    \onslide<7->{
        \node[above right=.5cm,yshift=1.33cm,xshift=2.75cm] (xms) at (current page.south west) {%
            \bjava{f(1) = 1}\only<8->{, \bjava{f(2) = 4}}\only<9->{, \bjava{f(3) =\ }\faFlash}
        };
        \onslide<10->{
            \node[below left,yshift=1mm] at(xms.south east) {
                \tiny\color{gray}\(\gtrsim 2 \uparrow^2 7 \approx 10^{10^{10^{19\,000}}}\)
            };
        }
    }
\end{tikzpicture}
\end{frame}
\subsection{Rekursive Strukturen}
\savebox\pinguA{\tikz{\pingu[wings wave, left eye devil=paletteA,right eye wink,large,hat=paletteA]}}%
\savebox\pinguB{%
\begin{minipage}{5cm}
\begin{plainjava}[morekeywords={[3]{T}}]^^J
class Node<T> \{^^J
\ \ Node left;^^J
\ \ Node right;^^J
\ \ T data;^^J
\}^^J
\end{plainjava}
\end{minipage}}%
\begin{frame}[fragile]{Rekursive Strukturen}
\begin{center}% two allows for better folding :D
\begin{columns}[c]
\begin{column}{.55\linewidth}
\centering\scalebox{.65}{\begin{tikzpicture}
    \onslide<2->{\node[lblob] (0) at (0,0) {};
    \node[lblob={fill=shadeA, draw=shadeA}] (1) at (-1.5,-1) {};
    \node[lblob] (2) at (1.5,-1) {};
    \node[lblob] (3) at (-2.5,-2) {};
    \node[lblob] (4) at (-.5,-2) {};
    \graph[edges={very thick,lgray,-Kite}]{(0) -> (1), (0) -> (2)};
    \graph[edges={very thick,shadeA,-Kite}]{(1) -> (3), (1) -> (4)};
    \node[below=4mm,font=\sffamily\footnotesize] at (current bounding box.south) {Jeder Knoten ist die Wurzel eines Teilbaums};}
\end{tikzpicture}}
\end{column} \begin{column}{.35\linewidth}\lstfs{8}%
\begin{plainjava}[aboveskip=-10pt]
!*\onslide<3->*!class Node {
!*\onslide<3->*!    Node left;
!*\onslide<3->*!    Node right;
!*\onslide<3->*!    int data;
!*\onslide<3->*!}
\end{plainjava}
\end{column}
\end{columns}\vspace*{2em}
\begin{columns}[c]
\begin{column}{.55\linewidth}
\centering\scalebox{.65}{\begin{tikzpicture}
    \onslide<5->{\node[lblob] (0) at (0,0) {};
    \node[lblob={fill=shadeA, draw=shadeA}] (1) at (1,-.5) {};
    \node[lblob] (2) at (2,-1) {};
    \node[lblob] (3) at (3,-1.5) {};
    \node[lblob] (4) at (4,-2) {};
    \graph[edges={very thick,lgray,-Kite}]{(0) -> (1), (2) -> (3) -> (4)};
    \draw[shadeA,very thick,-Kite] (1) -- (2);
    \node[below=4mm,font=\sffamily\footnotesize] at (current bounding box.south) {Jedes Element ist Kopf einer Teilliste};}
\end{tikzpicture}}
\end{column} \begin{column}{.35\linewidth}\lstfs{8}
\begin{onlyenv}<6->
\begin{plainjava}[aboveskip=-10pt]
class Element {
    Element next;
    int data;
}
\end{plainjava}
\end{onlyenv}
\end{column}
\end{columns}
\end{center}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<4->{%
        \node[above right=-.85cm,scale=.6] (pingu) at (current page.south west) {\rotatebox[origin=c]{-45}{\usebox\pinguA}};
        \node[above=1mm,scale=.5,text width=5.5cm,align=center,yshift=-.45cm,xshift=-.65cm] at (pingu.north east) {\usebox\pinguB\\[1ex]Cooler mit Generics!\textsuperscript{\cite{dive:java-generics}}};
    }
\end{tikzpicture}%
\end{frame}

\savebox\pinguA{\tikz{\pingu[left wing grab, right wing shock,right eye wink, left eye shock,halo]}}%
\begin{frame}[c,fragile]{Einen Baum evaluieren}
\begin{columns}
\begin{column}{.4\linewidth}
\centering\scalebox{.7}{\begin{tikzpicture}
    \onslide<2->{\node[lblob] (0) at (0,0) {\strut\only<2-16|handout:1->{$*$}\only<17-|handout:0>{25}};
    \onslide<2-16|handout:1->{\node[lblob] (1) at (-1.5,-1) {\only<2-15|handout:1->{$+$}\only<16-|handout:0>{5}};}
    \onslide<2-16|handout:1->{\node[lblob] (2) at (1.5,-1) {5};}
    \onslide<2-15|handout:1->{\node[lblob] (3) at (-2.5,-2) {2};}
    \onslide<2-15|handout:1->{\node[lblob] (4) at (-.5,-2) {3};}
    \onslide<2-16|handout:1->{\graph[edges={very thick,lgray,-Kite}]{(0) -> (1), (0) -> (2)};}
    \onslide<2-15|handout:1->{\graph[edges={very thick,lgray,-Kite}]{(1) -> (3), (1) -> (4)};}
    \node[below=4mm,font=\sffamily\footnotesize] at (current bounding box.south) {Ein Arithmetik-\only<2-16|handout:1->{Baum}\only<17-|handout:0>{Traum}!};}
\end{tikzpicture}}\\[1.25ex]
\lstfs{8}%
\begin{uncoverenv}<3->
\begin{plainjava}
    class Node {
        Node left, right;
        int data; String op;
    }
\end{plainjava}
\end{uncoverenv}
\end{column}
\begin{column}{.575\linewidth}
\begin{uncoverenv}<5->
\lstfs{8}%
\begin{plainjava}[aboveskip=0pt,belowskip=0pt,escapeinside={!}{!}]
!\onslide<5->!long postOrderEval(Node node) {
!\onslide<6->!    if(node == null) throw new /* ... */;
!\mdl[1]{13}\onslide<7->!    if(node.op == null) // no operation
!\mdl[1]{13}\onslide<7->!        return node.data;
!\mdl[2]{14}\onslide<8->!    long l = postOrderEval(node.left);
!\mdl[2]{14}\onslide<8->!    long r = postOrderEval(node.right);
!\mdl[2]{14}\onslide<9->!    switch(node.op) {
!\mdl[2]{14}\onslide<9->!        case "+": !\onslide<10->!return l + r;
!\mdl[2]{14}\onslide<9->!        case "*": !\onslide<11->!return l * r;
!\mdl[2]{14}\onslide<12->!        // ... other cases, errors, ...
!\mdl[2]{14}\onslide<9->!    }
!\onslide<5->!}
\end{plainjava}
\end{uncoverenv}\onslide<1->
\end{column}
\end{columns}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<4->{%
        \node[above right=.25cm,yshift=1cm,scale=.6] (pingu) at (current page.south west) {\usebox\pinguA};
        \node[above=1mm,xshift=.55cm,scale=.625,text width=4.25cm,align=center,font=\footnotesize\sffamily] at(pingu.north) {%
        An sich würde man die Knoten anders realisieren.
        Z.B. durch Vererbung.};
    }
\end{tikzpicture}
\end{frame}
% Eine Funktion auf Listen und eine auf Bäumen

\subsection{Weitere Probleme}
\savebox\pinguA{\tikz{\pingu[wings shock,princess crown,eyes shiny,small,belly=\Large\faHeart,princess crown gem colors={paletteA}{paletteB}{paletteC}{paletteB}{paletteA}]}}%
\savebox\pinguB{\tikz{\pingu[right eye wink,sign post left={\textbf{More!}},left wing wave,right wing grab,tie=paletteB]}}%
\begin{frame}[c]{Die Welt rekursiver Probleme}
\centering\columnsep30pt\begin{multicols}{2}
    \begin{enumerate}
        \itemsep10pt
        \item<3-> Rekursives Sortieren
\begin{center}
\resizebox{\linewidth}!{\begin{tikzpicture}[lgray,b/.style={decoration={brace,mirror,amplitude=4pt},very thick,decorate}]
    \onslide<4->{\node[lblob] (0) at (0,0) {};
    \node[lblob] (1) at (1,0) {};
    \node[lblob] (2) at (2,0) {};
    \node[lblob] (3) at (3,0) {};
    \node[lblob] (4) at (4,0) {};
    \node[lblob] (5) at (5,0) {};
    \node[lblob] (6) at (6,0) {};}
    \onslide<5|handout:1>{
        \draw[b] ([yshift=-2mm]0.south west) -- ([yshift=-2mm]3.south east);
        \draw[b] ([yshift=-2mm]4.south west) -- ([yshift=-2mm]6.south east);
    }
    \onslide<6|handout:0>{
        \draw[b] ([yshift=-2mm]0.south west) -- ([yshift=-2mm]1.south east);
        \draw[b] ([yshift=-2mm]2.south west) -- ([yshift=-2mm]3.south east);
        \draw[b] ([yshift=-2mm]4.south west) -- ([yshift=-2mm]5.south east);
        \draw[b] ([yshift=-2mm]6.south west) -- ([yshift=-2mm]6.south east);
    }
    \onslide<7-|handout:0>{
        \foreach \i in {0, ..., 6} {
            \draw[b] ([yshift=-2mm]\i.south west) -- ([yshift=-2mm]\i.south east);
        }
    }
\end{tikzpicture}}\medskip
\end{center}
        \item<8-> Die Türme von Hanoi
\begin{center}
\resizebox{\linewidth}!{\begin{tikzpicture}[lightgray,rounded corners=1pt]
    \onslide<9-|handout:1>{
        \foreach \i in {1.5, 3, 4.5} {
            \fill[lgray]  (\i,0) -| ++(1,.1) -|++(-.45,.55) -| ++(-.1,-.55) -| cycle;
        }
    }
    \onslide<9|handout:0>{
        \fill (1.5 + .1,.1) rectangle ++(.8,.1);
        \fill (1.5 + .2,.2) rectangle ++(.6,.1);
        \fill (1.5 + .3,.3) rectangle ++(.4,.1);
    }
    \onslide<10|handout:0>{
        \fill (1.5 + .1,.1) rectangle ++(.8,.1);
        \fill (1.5 + .2,.2) rectangle ++(.6,.1);
        \fill[shadeA] (4.5 + .3,.1) rectangle ++(.4,.1);
    }
    \onslide<11|handout:0>{
        \fill (1.5 + .1,.1) rectangle ++(.8,.1);
        \fill[shadeA] (3 + .2,.1) rectangle ++(.6,.1);
        \fill (4.5 + .3,.1) rectangle ++(.4,.1);
    }
    \onslide<12|handout:1>{
        \fill (1.5 + .1,.1) rectangle ++(.8,.1);
        \fill (3 + .2,.1) rectangle ++(.6,.1);
        \fill[shadeA] (3 + .3,.2) rectangle ++(.4,.1);
    }
    \onslide<13|handout:0>{
        \fill[shadeA] (4.5 + .1,.1) rectangle ++(.8,.1);
        \fill (3 + .2,.1) rectangle ++(.6,.1);
        \fill (3 + .3,.2) rectangle ++(.4,.1);
    }
    \onslide<14|handout:0>{
        \fill (4.5 + .1,.1) rectangle ++(.8,.1);
        \fill (3 + .2,.1) rectangle ++(.6,.1);
        \fill[shadeA] (1.5 + .3,.1) rectangle ++(.4,.1);
    }
    \onslide<15|handout:0>{
        \fill (4.5 + .1,.1) rectangle ++(.8,.1);
        \fill[shadeA] (4.5 + .2,.2) rectangle ++(.6,.1);
        \fill (1.5 + .3,.1) rectangle ++(.4,.1);
    }
    \onslide<16|handout:0>{
        \fill (4.5 + .1,.1) rectangle ++(.8,.1);
        \fill (4.5 + .2,.2) rectangle ++(.6,.1);
        \fill[shadeA] (4.5 + .3,.3) rectangle ++(.4,.1);
    }
    \onslide<17-|handout:0>{
        \fill (4.5 + .1,.1) rectangle ++(.8,.1);
        \fill (4.5 + .2,.2) rectangle ++(.6,.1);
        \fill (4.5 + .3,.3) rectangle ++(.4,.1);
    }
\end{tikzpicture}}\medskip
\end{center}
        \item<17-> Das N-Damen Problem
\begin{center}
\resizebox{.55\linewidth}!{\begin{tikzpicture}[lgray,rounded corners=1pt]
    \onslide<18-|handout:1>{
        \draw[thick] (0,0) grid ++(5,5);
    }
    \onslide<19-|handout:1>{
        \node[scale=.38] at(.5,1.5) {\usebox\pinguA};
        \node[scale=.38] at(3.5,.5) {\usebox\pinguA};
        \node[scale=.38] at(2.5,2.5) {\usebox\pinguA};
        \node[scale=.38] at(4.5,3.5) {\usebox\pinguA};
        \node[scale=.38] at(1.5,4.5) {\usebox\pinguA};
    }
\end{tikzpicture}}\medskip
\end{center}
    \end{enumerate}
\end{multicols}\bigskip
\begin{center}
    \footnotesize\onslide<21->{Alles was sich in (eventuell explorative) Einzelschritte zerteilen lässt.}
\end{center}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<20->{%
        \node[above right=.25cm,yshift=1cm,scale=.55] (pingu) at (current page.south west) {\usebox\pinguB};
        \node[above=1mm,scale=.6,text width=4.5cm,align=center,font=\footnotesize\sffamily,xshift=.85cm] at(pingu.north) {%
            \begin{itemize}
                \item Sudokus
                \item Wegfindung
                \item \href{https://introcs.cs.princeton.edu/java/32class/Hilbert.java.html}{Hilbert-Kurven}
                \item \ldots
            \end{itemize}
        };
    }
\end{tikzpicture}
\end{frame}
\subsubsection{Sorting}
\begin{frame}[fragile]{Rekursives Sortieren\hfill{\color{shadeA}\footnotesize\sbfamily Quicksort}}\lstfs{8}
\begin{plainjava}
!*\onslide<2->*!void quicksort(int[] arr) {
!*\onslide<3->*!    quicksort(arr, 0, arr.length - 1);
!*\onslide<2->*!}
!*\onslide<2->*!
!*\onslide<4->*!void quicksort(int[] arr, int left, int right) {
!*\onslide<5->*!    if(low >= right) return;
!*\onslide<6->*!    int partIndex = partition(arr, left, right);!*\tikzmark{partitionfunc}*!
!*\onslide<7->*!    quicksort(arr, left, partIndex - 1);
!*\onslide<7->*!    quicksort(arr, partIndex + 1, right);
!*\onslide<4->*!}
\end{plainjava}
\begin{tikzpicture}[overlay,remember picture]
\onslide<8->{\node[below right,xshift=1cm,gray,scale=.55,text width=4cm] (bzt) at (pic cs:partitionfunc) {%
    Wählt Pivot und sortiert kleiner Pivotelement links und größer gleich rechts.%
};
\draw[lgray,thick,-Kite] (bzt.north west) to[out=135,in=0] (pic cs:partitionfunc);}
\end{tikzpicture}
\end{frame}
\subsubsection{Die Türme von Hanoi}
\savebox\pinguA{\begin{tikzpicture}[lightgray,rounded corners=1pt]
    \foreach \i/\a in {1.5/A, 3/B, 4.5/C} {
        \fill[lgray]  (\i,0) -| ++(1,.1) -|++(-.45,.55) -| ++(-.1,-.55) -| cycle;
        \node[below=1mm,gray] at(\i+.5,0) {\a};
    }
    \fill (1.5 + .1,.1) rectangle ++(.8,.1);
    \fill (1.5 + .2,.2) rectangle ++(.6,.1);
    \fill (1.5 + .3,.3) rectangle ++(.4,.1);
\end{tikzpicture}}
\savebox\pinguB{\tikz{\pingu[wings wave, princess crown 2d=pingu@bronze,belly=\Large\faCode,sunglasses round, glasses opacity=.975]}}%
\savebox\pinguC{%
\begin{minipage}{5cm}%
\begin{plainjava}[morekeywords={[3]{Pole}}]^^J
enum Pole \{^^J
\ \ SOURCE,^^J
\ \ HELPER,^^J
\ \ TARGET^^J
\}^^J
\end{plainjava}
\end{minipage}}%
\begin{frame}[fragile]{Die Türme von Hanoi}
\begin{tikzpicture}[remember picture,overlay]
    \onslide<2->{\node[below left=.33cm] at (current page.north east) {\usebox\pinguA};}
    \onslide<7->{%
        \node[above right=.25cm,yshift=1cm,scale=.6] (pingu) at (current page.south west) {\usebox\pinguB};
        \node[above=1mm,xshift=.85cm,scale=.75,text width=4.5cm,align=left,font=\footnotesize\sffamily] at(pingu.north) {\usebox\pinguC};
    }
    \onslide<13->{%
        \node[below right,xshift=.75cm, gray,scale=.55,text width=5.5cm,yshift=.25cm] (move-desc) at (pic cs:move-after) {%
            Gibt im einfachsten Fall einfach \say{$a \to c$} aus.%
        };
        \draw[-Kite,lgray,thick] (move-desc.178) to[out=175,in=0] ([yshift=2pt]pic cs:move-after);
    }
\end{tikzpicture}%
\scriptsize\begin{itemize}
    \item<3-> Trivial für eine Scheibe: \(A \to C\).
    \item<4-> Sonst: \begin{itemize}
        \item<4-> \strut\scriptsize Bewege \(n - 1\) Scheiben auf Hilfsstapel: \(A \to B\).
        \item<5-> \strut\scriptsize Bewege letzte Scheibe (größte) von \(A \to C\).
        \item<6-> \strut\scriptsize Bewege \(n - 1\) Scheiben vom Hilfsstapel zum Ziel: \(B \to C\).
    \end{itemize}
\end{itemize}\normalsize\lstfs{7}
\begin{plainjava}[morekeywords={[3]{Pole}}, morekeywords={[4]{move}}]
!*\onslide<8->*!void hanoi(int disks, Pole a, Pole b, Pole c) {
!*\onslide<9->*!    if(disks == 1) { move(a, c);!*\tikzmark{move-after}*! }
!*\onslide<9->*!    else {
!*\onslide<10->*!        hanoi(disks - 1, a, c, b); // move all disks above to help pole
!*\onslide<11->*!        move(a, c); // move last disk to target
!*\onslide<12->*!        hanoi(disks - 1, b, a, c); // move disks from help to target pole
!*\onslide<9->*!    }
!*\onslide<8->*!}
\end{plainjava}
\end{frame}

\subsubsection{Das N-Damen Problem}
\savebox\pinguA{%
\begin{minipage}{7.35cm}
\begin{plainjava}^^J
boolean nQueens(boolean[][] board) \{^^J
\ \ return nQueens(board, 0);^^J
\}^^J
\end{plainjava}
\end{minipage}
}
\savebox\pinguB{\tikz{\pingu[right eye wink,sign post right={\textbf{Task}}, sign post right color=paletteA,right wing wave,left wing grab,medal=paletteA,medal text=!]}}%
\savebox\pinguC{\tikz{\pingu[wings shock,princess crown,eyes shiny,small,belly=\Large\faHeart,princess crown gem colors={paletteA}{paletteB}{paletteC}{paletteB}{paletteA}]}}%
\begin{frame}[fragile]{Das N-Damen Problem}\lstfs{8}
\begin{tikzpicture}[overlay,remember picture]
    \onslide<2->{\node[below left=.33cm,fill=lgray!30!white,rounded corners=2pt,scale=.65] at (current page.north east) {\usebox\pinguA};}
    \onslide<11->{
        \node[above right=.33cm,scale=.65,yshift=.5cm] (pingu) at (current page.south west) {\usebox\pinguB};
        \node[gray,above=1mm,text width=4cm,scale=.8,align=center] at(pingu.north) {%
            \scriptsize Wie könnte man \bjava{queenCanBePlacedHere} umsetzen?%
        };
    }
    \scope[shift={(current page.south east)},shift={(-1,1.65)},scale=.55]
    \onslide<12->{
        % field
        \draw[lgray,thick] (0,0) grid (-4,4);
        \foreach \i in {0, 1, 2, 3} {
            \node[gray,left] at(-4,\i+.5) {\i};
            \node[gray,below] at(-\i-.5,0) {\the\numexpr3-\i};
        }
        \onslide<12-17|handout:0>{\node[right,shadeA] at (0,.5) {\faChevronLeft};}
        \onslide<18-27,39-44|handout:0>{\node[right,shadeA] at (0,1.5) {\faChevronLeft};}
        \onslide<28-38,45-49|handout:0>{\node[right,shadeA] at (0,2.5) {\faChevronLeft};}
        \onslide<50-|handout:1>{\node[right,shadeA] at (0,3.5) {\faChevronLeft};}
        \onslide<14-15|handout:0>{\fill[shadeA] (-3.5,.5) circle[radius=2.33mm];}
        \onslide<16-49|handout:0>{\node[scale=.215] at(-3.5,.5) {\usebox\pinguC};}
        \onslide<20-21|handout:0>{\fill[shadeA] (-3.5,1.5) circle[radius=2.33mm];}
        \onslide<22-23|handout:0>{\fill[shadeA] (-2.5,1.5) circle[radius=2.33mm];}
        \onslide<24-25|handout:0>{\fill[shadeA] (-1.5,1.5) circle[radius=2.33mm];}
        \onslide<26-39|handout:0>{\node[scale=.215] at(-1.5,1.5) {\usebox\pinguC};}
        \onslide<30-31|handout:0>{\fill[shadeA] (-3.5,2.5) circle[radius=2.33mm];}
        \onslide<32-33|handout:0>{\fill[shadeA] (-2.5,2.5) circle[radius=2.33mm];}
        \onslide<34-35|handout:0>{\fill[shadeA] (-1.5,2.5) circle[radius=2.33mm];}
        \onslide<36-38|handout:0>{\fill[shadeA] (-.5,2.5) circle[radius=2.33mm];}
        \onslide<40|handout:0>{\fill[shadeA] (-1.5,1.5) circle[radius=2.33mm];}
        \onslide<41-42|handout:0>{\fill[shadeA] (-.5,1.5) circle[radius=2.33mm];}
        \onslide<43-49|handout:0>{\node[scale=.215] at(-.5,1.5) {\usebox\pinguC};}
        \onslide<47-48|handout:0>{\fill[shadeA] (-3.5,2.5) circle[radius=2.33mm];}
        \onslide<50-|handout:1>{
            \node[scale=.215] at(-3.5,1.5) {\usebox\pinguC};
            \node[scale=.215] at(-2.5,3.5) {\usebox\pinguC};
            \node[scale=.215] at(-1.5,.5) {\usebox\pinguC};
            \node[scale=.215] at(-.5,2.5) {\usebox\pinguC};
        }
        % stack trace
        \onslide<12-|handout:1>{ \node[lblock,scale=.75,inner sep=1pt] (q0) at (-6.75,3.5) {\bjava{q(board, 0)}}; }
        \onslide<18-49|handout:0>{ \node[lblock,scale=.75,inner sep=1pt] (q1) at (-6.75,2) {\bjava{q(board, 1)}}; \draw[lgray,thick,-Kite] (q0) -- (q1); }
        \onslide<28-38,45-49|handout:0>{ \node[lblock,scale=.75,inner sep=1pt] (q2) at (-6.75,.5) {\bjava{q(board, 2)}}; \draw[lgray,thick,-Kite] (q1) -- (q2); }
        \onslide<49|handout:0>{\fill[lgray,fill opacity=.42,rounded corners=4pt] (1.25,-1.25) rectangle (-8.5,4.25) node[midway,centered,text=black] {\huge\textbf{\ldots}};}
    }
    \endscope
\end{tikzpicture}
\begin{plainjava}
!*\md{12,18,28,45}\onslide<3->*!boolean nQueens(boolean[][] board, int row) {
!*\md{13,19,29,46}\onslide<4->*!    if(row == board.length) return true;
!*\md{14,20,22,24,30,32,34,36,41,47}\onslide<5->*!    for (int column = 0; column < board.length; column++) {
!*\md{15,21,23,25,31,33,35,37,42,48}\onslide<6->*!        if(!queenCanBePlacedHere(board, column, row)) continue;
!*\md{16,26,43}\onslide<7->*!        board[row][column] = true; // Try to place queen here
!*\onslide<8->*!        if(!*\mh{17,27,44}*!nQueens(board, row + 1)!*\mh{39}*!)
!*\onslide<8->*!            return true;!*\mh[1]{50}*!
!*\onslide<9->\md{40}*!        board[row][column] = false;
!*\onslide<5->*!    }
!*\onslide<10->\md{38}*!    return false;
!*\onslide<3->*!}
\end{plainjava}
\end{frame}
% darüber setzen und einmal durch animieren?

\section{Abschluss}
\savebox\pinguA{\tikz{\pingu[small, eye patch left, sign post left={\textbf{\ldots}}, hair=paletteA]}}
\savebox\pinguB{\tikz{\pingu[eyes wink,small,left wing wave,sign post left={\textbf{\ldots}},devil horns=pingu@main]}}
\savebox\pinguC{\tikz{\pingu[eyes shiny,small, left wing hug,straw hat,sign post left={\textbf{\ldots}},belly={\Large\textbf{\ldots}}]}}
\SidebarCite{dive:tail-recursion}
\begin{frame}[c]{Das obligatorische \say{Übrigens\ldots}}
    \begin{itemize}[<+(1)->]
        \itemsep10pt
        \item Viele Varianten: \begin{itemize}
            \itemsep3pt
            \item Tail-Rekursionen
            \item Primitiv-Rekursive Funktionen
        \end{itemize}
        \item Stack-Frames sind spannender und enthalten noch mehr!
        \item Das riesige Thema des Compilerbaus liefert mehr:
        \begin{itemize}
            \itemsep3pt
            \item Optimierungen \& Transformationen
            \item Recursive Descent Parser
        \end{itemize}
        \item \parbox[t]{5.05cm}{Dynamische Programmierung!}
    \end{itemize}
\begin{tikzpicture}[remember picture, overlay]
    \onslide<10->{\node[scale=.6,above left=.5cm,yshift=1.25cm,xshift=-7.65cm] (p1) at(current page.south east) {\usebox\pinguA};}
    \onslide<11->{\node[scale=.6,above right] (p2) at(p1.south east) {\usebox\pinguB};}
    \onslide<12->{\node[scale=.6,above right] (p3) at(p2.south east) {\usebox\pinguC};}
\end{tikzpicture}
\end{frame}
\SidebarReset
\newsavebox\javaStackBox \savebox\javaStackBox{%
\begin{tikzpicture}
    \fill[lgray,rounded corners] (0,0) rectangle ++(3,5.5);
    \fill[lgray,rounded corners] (3.5,0) rectangle ++(3,5.5);
    \node[ldesc,below] at (1.5,0) {Stack};
    \node[ldesc,below] at (5,0) {Heap};
    \node[lrel] at (1.5,5) {\ldots};
    \node[lrel] at (5,5) {\ldots};
    \node[lrel] at (1.5,5-.85) {\bjava{int x = 0}};
    \node[lrel] at (1.5,5-.85*2) {\bjava{byte y = 12}};
    \node[lrel] (fg) at (1.5,5-.85*3) {\bjava{String f =\ }\raisebox{-1pt}\faGenderless};
    \node[lrel] (ft) at (5,5-.85-.425) {\bjava{\"Hallo Welt\"}};
    \draw[lightgray,very thick,-Kite]  (fg.east) to[out=0,in=180] (ft.west);
    \node[lrel] (cg) at (1.5,5-.85*4) {\bjava{char[] c =\ }\raisebox{-1pt}\faGenderless};
    \node[lrel] (ct) at (5,5-.85*4) {\bjava{\{2, 3, 4\}}};
    \draw[lightgray,very thick,-Kite]  (cg.east) -- (ct.west);
\end{tikzpicture}
}
\newsavebox\javaStackFrames \savebox\javaStackFrames{
\begin{tikzpicture}
\fill[lgray,rounded corners] (0,-.5) rectangle ++(3.5,5.5);
\node[ldesc,below] at (1.75,-.5) {Stack};
\node[lrel,minimum width=33mm] (ld) at (1.75,5-.495) {\ldots};
\node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (s) at(ld.south) {%
    \T{f}
    \nodepart{second}
    \bjava{int x = 3}
};
\draw[ultra thick,lgray] (s.text split west) -- (s.text split east);
\node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (d) at (s.south) {%
    \T{f}
    \nodepart{second}
    \bjava{int x = 2}
};
\draw[ultra thick,lgray] (d.text split west) -- (d.text split east);
\node[lsf,minimum width=33mm,minimum height=28mm,below=1mm] (f3) at (d.south) {%
\T{f}
\nodepart{second}
\bjava{int x = 1}
};
\draw[ultra thick,lgray] (f3.text split west) -- (f3.text split east);
\end{tikzpicture}}
\newsavebox\recursionVariants \savebox\recursionVariants{%
\begin{tikzpicture}[lblob/.append style={text=black,scale=.8},xscale=1.33]
    \node[lblob] (0) at(0,0) {\T{a(42)}};
    \node[lblob] (1) at(2,-.75) {\T{b(41)}}; \draw[lgray,thick,-Kite] (0) -- (1);
    \node[lblob] (2) at(0,-1.5) {\T{a(2)}}; \draw[lgray,thick,-Kite] (1) -- (2);
    \node[lblob] (3) at(2,-2.25) {\T{b(1)}}; \draw[lgray,thick,-Kite] (2) -- (3);
    \node[lblob] (4) at(0,-3) {\T{a(1)}}; \draw[lgray,thick,-Kite] (3) -- (4);
    \node[lblob] (5) at(2,-3.75) {\T{b(0)}}; \draw[lgray,thick,-Kite] (4) -- (5);
    \node[gray,right=1mm,scale=.9] at (5.east) {0};
    \node[gray,left=1mm,scale=.9] at (4.west) {0}; \draw[lgray,thick,-Kite] (5) to[bend right=20] (4);
    \node[gray,right=1mm,scale=.9] at (3.east) {0}; \draw[lgray,thick,-Kite] (4) to[bend left=20] (3);
    \node[gray,left=1mm,scale=.9] at (2.west) {0}; \draw[lgray,thick,-Kite] (3) to[bend right=20] (2);
    \node[gray,right=1mm,scale=.9] at (1.east) {0}; \draw[lgray,thick,-Kite] (2) to[bend left=20] (1);
    \node[gray,left=1mm,scale=.9] at (0.west) {0}; \draw[lgray,thick,-Kite] (1) to[bend right=20] (0);
\end{tikzpicture}}
\newsavebox\recursiveStructures \savebox\recursiveStructures{%
\begin{tikzpicture}
    \node[lblob] (0) at (0,0) {};
    \node[lblob={fill=shadeA, draw=shadeA}] (1) at (-1.5,-1) {};
    \node[lblob] (2) at (1.5,-1) {};
    \node[lblob] (3) at (-2.5,-2) {};
    \node[lblob] (4) at (-.5,-2) {};
    \graph[edges={very thick,lgray,-Kite}]{(0) -> (1), (0) -> (2)};
    \graph[edges={very thick,shadeA,-Kite}]{(1) -> (3), (1) -> (4)};
\end{tikzpicture}}
\newsavebox\towersHanoi \savebox\towersHanoi{%
\begin{tikzpicture}[lightgray,rounded corners=1pt]
    \foreach \i in {1.5, 3, 4.5} {
        \fill[lgray]  (\i,0) -| ++(1,.1) -|++(-.45,.55) -| ++(-.1,-.55) -| cycle;
    }
    \fill (1.5 + .1,.1) rectangle ++(.8,.1);
    \fill (3 + .2,.1) rectangle ++(.6,.1);
    \fill[shadeA] (3 + .3,.2) rectangle ++(.4,.1);
\end{tikzpicture}}
\begin{frame}[c]{~}
\begin{center}
    \only<2-4|handout:1>{\begin{tabular}{*3{>{\centering\arraybackslash}m{.3\linewidth}}}
        \onslide<2->{\scalebox{.5}{\usebox\javaStackBox}} & \onslide<3->{\scalebox{.5}{\usebox\javaStackFrames}} & \onslide<4->{\scalebox{.5}{\usebox\recursionVariants}} \\
        \onslide<2->{\footnotesize Speicherverwaltung} & \onslide<3->{\footnotesize Stack Frames} & \onslide<4->{\footnotesize Rekursionstypen}
    \end{tabular}}
    \only<5-|handout:2>{\begin{tabular}{*3{>{\centering\arraybackslash}m{.3\linewidth}}}
        \onslide<6->{\scalebox{.65}{\(f(n) = \begin{cases}
        1,\quad & n \leq 1 \\
        n \cdot f(n - 1),\quad & n > 1
    \end{cases}\)}} & \onslide<7->{\scalebox{.65}{\usebox\recursiveStructures}} & \onslide<8->{\scalebox{.85}{\usebox\towersHanoi}} \\
        \onslide<6->{\footnotesize Mathematisch} & \onslide<7->{\footnotesize Datenstrukturen} & \onslide<8->{\footnotesize Divide- \& Conquer}
    \end{tabular}}
\end{center}
\end{frame}
\end{document}