% vim: set spelllang=nl:
\subsubsection{Het recursieve binnenste programma}
Het binnenste programma draait strings van lengte n + 1 om. Hiervoor krijgt het
twee "argumenten" geprepend mee. Het eerste argument is een string in zijn
oorspronkelijke volgorde, die elke recursieve aanroep \'{e}\'{e}n karakter
kleiner wordt. Het tweede argument is een string die initi\"{e}el de lege
string is, maar bij elke recursieve aanroep \'{e}\'{e}n karakter groter wordt
en de omgekeerde string voorstelt. De reden dat dit programma alleen voor
strings van lengte n + 1 werkt is als volgt: het testen van waarden kost zoals
we eerder hadden gezien een programma-aanroep. Wij hebben ervoor gekozen om
eerst de string te verkleinen en daarna te kijken of we de lege string hebben
bereikt (de hele string is omgedraaid) om te bepalen of we dit programma nog
eens moeten uitvoeren met nieuwe argumenten. Als je zou willen bepalen of je
inputstring leeg was voordat je deze verkleint zou je 2 recursieve programma's
nodig hebben die elkaar telkens aanroepen: \'{e}\'{e}n die als eerste test of
de input leeg en daarop gebaseerd \'{o}f het andere programma aanroept \'{o}f
output geeft en eindigt en een ander programma dat de string verkleint en dan
het eerste programma aanroept om weer de waarde te testen. Het leek ons dus
beter om aan het einde te testen of we door moeten gaan en het geval van de
lege string op te vangen in het buitenste programma.

Het recursieve omdraaiprogramma ziet er zo uit:

\begin{center}
\makebox{
\parbox{48mm}{
\begin{smurf}
\footnotesize
\emph{x-string} \emph{y-string}\\
"\textbackslash"program\textbackslash"p\textbackslash"grow\textbackslash"p\textbackslash"shrink\textbackslash"p\\
\textbackslash"shrink\textbackslash"gh\textbackslash"grow\textbackslash"g+\textbackslash"grow\textbackslash"p\\
\textbackslash"shrink\textbackslash"gt\textbackslash"shrink\textbackslash"p\textbackslash"shrink\textbackslash"g\\
\textbackslash"grow\textbackslash"gq\textbackslash"o\textbackslash"+\textbackslash"shrink\textbackslash"gq\\
\textbackslash"grow\textbackslash"gq\textbackslash"program\textbackslash"gq++\textbackslash"program\\
\textbackslash"g+\textbackslash"shrink\textbackslash"gp\textbackslash"\textbackslash"pgx"\\
\vspace{\baselineskip}
"program" p\\
"grow" p\\
"shrink" p\\
\vspace{\baselineskip}
"shrink" g h\\
"grow" g + "grow" p\\
"shrink" g t "shrink" p\\
\vspace{\baselineskip}
"shrink" g\\
\vspace{\baselineskip}
"grow" g q "o" +\\
\vspace{\baselineskip}
"shrink" g q "grow" g q\\
"program" g q + +\\
"program" g +\\
\vspace{\baselineskip}
"shrink" g p\\
\vspace{\baselineskip}
"" p\\
\vspace{\baselineskip}
g x
\end{smurf}
}

\parbox{8mm}{
\begin{smurf}
\footnotesize
(1)\\
(2)\\
.\\
.\\
.\\
.\\
.\\
.\\
(3)\\
.\\
.\\
.\\
(4)\\
.\\
(5)\\
.\\
(6)\\
.\\
(7)\\
.\\
(8)\\
.\\
.\\
.\\
(9)\\
.\\
(10)\\
.\\
(11)
\end{smurf}
}}
\end{center}

\textbf{(1)} De argumenten worden er de eerste keer opgezet door het buitenste
programma. Merk op dat het y-argument in het buitenste programma
\texttt{"\textbackslash"\textbackslash""} is, wat de gequotifyde versie is van
\texttt{""}, oftewel de lege string. Het x-argument is dan de niet-lege input.
\textbf{(2)} Hierna wordt de een string van de rest van het programma (vanaf
(3)) op de stack gezet. Dit zorgt ervoor dat recursie mogelijk is.
\textbf{(3)} Het programma en de argumenten worden in variabelen opgeslagen.
"program" voor het programma, "grow" voor het rechterargument, "shrink" voor
het linkerargument.  \textbf{(4)} De waarde van "shrink" wordt opgehaald en
vervangen door zijn eerste karakter. Daarna wordt "grow" opgehaald en het
eerste karakter van "shrink" wordt eraan geappend. Het resultaat hiervan wordt
weggeschreven naar "grow".  \textbf{(5)} Nu wordt de waarde van "shrink" nog
eens opgehaald, vervangen door zijn tail en weer teruggeschreven naar "shrink".
Nu is het eerste karakter van shrink dus naar achter "grow" verplaatst.
\textbf{(6)} De nieuwe waarde van "shrink" wordt nu al vast op de stack gezet,
voor dezelfde reden dat dit in het buitenste programma met "input" gebeurde.
Wanneer we hem later nodig hebben hebben we niet de garantie dat de
variabelenaam niet overschreven is, dus we zetten hem er nu al op.
\textbf{(7)} De nieuwe waarde van "grow" wordt opgehaald en gequotifyed. Ook
appenden we "o" eraan. Zo vormt het een programmastring die die waarde zou
outputten wanneer uitgevoerd. Dit moeten we doen als "shrink" leeg is geworden.
Merk op dat het programma dat moet worden uitgevoerd wanneer de string leeg is
geworden in tegenstelling tot in het buitenste programma hier v\'{o}\'{o}r het
andere programma wordt aangemaakt. Dit doen we omdat we hier een waarde van een
variabele gebruiken en we niet weten of de variabele straks overschreven wordt.
We bouwen deze programmastring dus al vast, maar laten hem nog gewoon op de
stack staan.  \textbf{(8)} "shrink" en "grow" worden opgehaald en gequotifyed.
Ook "program" wordt opgehaald en gequotifyed. Dit alles appenden we aan elkaar.
Nu wordt "program" nog eens opgehaald, niet gequotifyed en aan de eerdere sting
geappend. Nu is deze hele string gelijk aan het hele programma, maar met de
nieuwe waarden van "grow" en "shrink" als argumenten.  \textbf{(9)} Nu komt het
deel waar we de waarde van shrink testen om te kiezen of we output moeten
geven, of nog een recursiestap moeten uitvoeren. De waarde van "shrink" wordt
opgehaald en gebruikt als variabelenaam om het programma dat we in (8) hadden
gebouwd naar weg te schrijven. Vanaf dit punt kunnen we geen van onze
variabelen meer gebruiken, omdat de waarde van "shrink" toevallig gelijk zou
kunnen zijn geweest aan de naam van een van onze variabelen.  \textbf{(10)} Nu
schrijven we het programma dat we in (7) hadden gebouwd en nog op de stack
stond weg naar de variabele met naam de lege string.  \textbf{(11)} Nu halen we
de waarde op van de variabele met als naam de waarde van "shrink" die we in (6)
al op de stack hadden gezet. Als "shrink" leeg was vinden we het programma uit
(7). Anders vinden we het programma uit (8). We voeren het gevonden programma
uit.
