Simple recursion in LaTeX

Question

I am trying to get into LaTeX recursion and created a command \tower[2][3][4][2] that returns a power tower, 2^{3^{4^2}}, for any number of arguments. My attempt:

\documentclass{beamer}
\usepackage{xparse}

\NewDocumentCommand\tower{o}{%
  \IfValueT{#1}{\towerstep{#1}}}
\NewDocumentCommand\towerstep{m}{%
   #1^\tower}

\begin{document}
    \begin{frame}
        \tower[2][3][4][2]
    \end{frame}
\end{document}

This produces a lot of errors, but it gives the correct output. The errors come from the expression not standing in mathmode (adding $ made things worse for me) and from missing braces. I suppose this has something to do with the order in which commands are expanded. How can I fix the code?

Answer 1

A solution in the spirit of the programmation by continuation:

\documentclass{article}
\usepackage{xparse}

\ExplSyntaxOn
\NewDocumentCommand \towerAux { m o }
  {
    \IfValueTF { #2 }
      { \towerAux {{#1}{#2}} }
      { \__tower:nn {#1} { } }
  }

\cs_set:Npn \__tower:nn #1 #2 
  {
    \tl_if_empty:nTF { #1 }
      { #2 }
      { \__tower_i:nnn #1 { #2 } }
  }

\cs_set:Npn \__tower_i:nnn #1 #2 #3 { \__tower:nn { #1 } { #2 ^ { #3 } } }

\NewDocumentCommand \tower { } { \towerAux { } }
\ExplSyntaxOff

\begin{document}
$\tower[5][3][4][2]$
\end{document}

With this programmation, $\tower[5][3][4][2]$ is replaced successively by the following instructions:

$\tower[5][3][4][2]$

$\towerAux{}[5][3][4][2]$

$\towerAux{{}{5}}[3][4][2]$

$\towerAux{{{}{5}}{3}}[4][2]$

$\towerAux{{{{}{5}}{3}}{4}}[2]$

$\towerAux{{{{{}{5}}{3}}{4}}{2}}$

As you see, \towerAux is recursive.

Now, all the arguments (if I can say) have been structured in a kind of list and the last one is the first accessible. You can now construct the required result in a kind of auxiliary argument (at the end) as usual in recursive programmation. The commands \__tower:nn and \__tower_i:nnn are mutually recursive.

$\__tower:nn{{{{{}{5}}{3}}{4}}{2}}{}$

$\__tower_i:nnn{{{{}{5}}{3}}{4}}{2}{}$

$\__tower:nn{{{{}{5}}{3}}{4}}{2^{}}$

$\__tower_i:nnn{{{}{5}}{3}}{4}{2^{}}$

$\__tower:nn{{{}{5}}{3}}{4^{2^{}}}$

$\__tower_i:nnn{{}{5}}{3}{4^{2^{}}}$

$\__tower:nn{{}{5}}{3^{4^{2^{}}}}$

$\__tower_i:nnn{}{5}{3^{4^{2^{}}}}$

$\__tower_i:nnn{}{5^{3^{4^{2^{}}}}}$

$5^{3^{4^{2^{}}}}$

Answer 2

\documentclass[border=15pt]{standalone}
\makeatletter
\def\tower{\@ifnextchar[{\def\endtower{}\towerstep}{}}%
\def\towerstep[#1]{#1%
  \@ifnextchar[{\edef\endtower{\endtower\egroup}^\bgroup\towerstep}{\endtower}}
\makeatother
\begin{document}
        $\tower[2][3][4][2]$ 
        $\tower[2][3][4]$ 
        $\tower[2][3]$ 
        $\tower[2]$ 
        $\tower$ 

\end{document}

Answer 3

I build two token lists, the first containing

{1^{2^{3^{4^{5^{6^{7

and the other containing

}}}}}}}

Actually, the braces are stored as \c_group_begin_token and \c_group_end_token, so the token lists are balanced.

If [ follows, a further step is taken. At the end, the two lists are delivered.

\documentclass{article}
\usepackage{xparse}

\ExplSyntaxOn
\NewDocumentCommand{\tower}{}
 {
  \tl_clear:N \l__perner_tower_left_tl
  \tl_clear:N \l__perner_tower_right_tl
  \perner_tower_build:n { }
 }

\tl_new:N \l__perner_tower_left_tl
\tl_new:N \l__perner_tower_right_tl

\cs_new_protected:Nn \perner_tower_build:n
 {
  \peek_charcode:NTF [
   {% there is a [
    \__perner_tower_add:nw { #1 }
   }
   {% no [, end
    \__perner_tower_end:
   }
 }
    
\cs_new_protected:Npn \__perner_tower_add:nw #1 [#2]
 {
  \tl_put_right:Nn \l__perner_tower_left_tl { #1 \c_group_begin_token #2 }
  \tl_put_right:Nn \l__perner_tower_right_tl { \c_group_end_token }
  \perner_tower_build:n { \c_math_superscript_token }
 }

\cs_new_protected:Npn \__perner_tower_end:
 {
  \tl_use:N \l__perner_tower_left_tl
  \tl_use:N \l__perner_tower_right_tl
 }
\ExplSyntaxOff

\begin{document}

$\tower[1][2][3][4][5][6][7]$

\end{document}

Much shorter with a different syntax. The argument is split at commas; then between any two items we output ^{ (again as implicit tokens) and at the end the right number of } is output.

\documentclass{article}
\usepackage{xparse}

\ExplSyntaxOn
\NewDocumentCommand{\tower}{m}
 {
  \perner_tower_build:n { #1 }
 }

\seq_new:N \l__perner_tower_seq

\cs_new_protected:Nn \perner_tower_build:n
 {
  \seq_set_split:Nnn \l__perner_tower_seq { , } { #1 }
  \seq_use:Nn \l__perner_tower_seq { \c_math_superscript_token \c_group_begin_token }
  \prg_replicate:nn { \seq_count:N \l__perner_tower_seq - 1 } { \c_group_end_token }
 }
\ExplSyntaxOff

\begin{document}

$\tower{1,2,3,4,5,6,7}$

\end{document}

Answer 4

Basically, your \tower macro expands into 2^3^4^2, and not into $2^{3^{4^{2}}}$, so there are two types of errors: missing math mode delimiter (^ makes sense only in math mode), and double superscript (TeX deliberately throws error for $a^b^c$ and doesn't try to guess which is correct, `${a^b}^c$ or $a^{b^c}$).

The problem with the code is that it should somehow collect all these }}} and put them at the end of the expansion. The following code does just that (I also put $$ for math mode):

\documentclass{beamer}
\usepackage{xparse}

\NewDocumentCommand\tower{}{\def\endtower{}\starttower}
\NewDocumentCommand\starttower{o}{%
  \IfValueTF{#1}{\edef\endtower{\endtower\egroup}\towerstep{#1}}{\endtower}}
\NewDocumentCommand\towerstep{m}{%
  #1^\bgroup\starttower}

\begin{document}
    \begin{frame}
        $\tower[2][3][4][2]$
    \end{frame}
\end{document}

Notice the \endtower macro which is empty initially, but every time \starttower executes and finds an optional argument (the next tower floor), it extends by another \egroup. \bgroup and \egroup are equivalent to { and } respectively, and they are easier to use in macro definitions in case if nonmatching braces are needed.

Answer 5

Perhaps like this:

\documentclass{beamer}
\usepackage{xparse}
%-----------------------------------------------------------------------------
% In case there is an optional argument \tower calls \towerreverseloop:
%-----------------------------------------------------------------------------
\NewDocumentCommand\tower{o}{%
  \IfValueT{#1}{\towerreverseloop{[{#1}]}}%
}%
%-----------------------------------------------------------------------------
% \towerreverseloop reverses the order of the list of optional arguments.
% #1 holds the reversed list of optional arguments gathered so far.
% #2 is the next optional argument.
% If there are no more optional arguments to put into reversed order, 
% then \towerinitializeconstructexpressionloop is applied to the reversed
% list of optional arguments gathered so far.
%-----------------------------------------------------------------------------
\NewDocumentCommand\towerreverseloop{mo}{%
  \IfValueTF{#2}{%
    \towerreverseloop{[{#2}]#1}%
  }{%
    \towerinitializeconstructexpressionloop#1%
  }%
}%
%-----------------------------------------------------------------------------
% \towerinitializeconstructexpressionloop calls \towerconstructexpressionloop,
% hereby initializing \towerconstructexpressionloop's "expression constructed
% so far"-argument with the first element of the reversed list of optional
% arguments.
%-----------------------------------------------------------------------------
\NewDocumentCommand\towerinitializeconstructexpressionloop{o}{%
  \towerconstructexpressionloop{#1}%
}%
%-----------------------------------------------------------------------------
% \towerconstructexpressionloop constructs the desired expression from the
% elements of the reversed list of optional arguments.
% #1 holds the expression constructed so far.
% #2 next optional argument/next element of the reversed list of
%    optional arguments.
%-----------------------------------------------------------------------------
\NewDocumentCommand\towerconstructexpressionloop{mo}{%
  \IfValueTF{#2}%
            {\towerconstructexpressionloop{#2^{#1}}}%
            {#1%
             %\def\result{#1}\show\result
            }%
}%
\begin{document}
    \begin{frame}[fragile]
        \verb|$\tower[2][3][4][2]$|: $\tower[2][3][4][2]$\\
        \verb|$\tower[2][3][4]$|: $\tower[2][3][4]$\\
        \verb|$\tower[2][3]$|: $\tower[2][3]$\\
        \verb|$\tower[2]$|: $\tower[2]$\\
        \verb|$\tower$|: $\tower$
    \end{frame}
\end{document}