# How to avoid input stack overflow during recursion

Although there is already a ↗question with a similar title, I take the risk of asking again, because the linked topic is a bit bloated in my opinion, the answers/solutions too complicated.

So here is a more generic example:

\def\recursion#1\nil{%
\ifnum#1>0
\expandafter\recursion\the\numexpr #1-1\relax\nil%
{#1}%
\else%
{Start}{0}%
\fi%
}

\edef\result{\recursion 4997\nil} %works up to 4996

\show\result %{Start}{0}{1}{2}{3}...'

\bye


It saves the result {Start}{0}{1}{2}{3}...{<initial value>} in \result. Thus, the wanted recursion macro is expected to be expandable.

With default settings of TeX Live, the code above only works for initial values up to 4996, but else fails with ! TeX capacity exceeded, sorry [input stack size=5000]., probably due to nesting of \ifnum... clauses.

In an attempt to solve the problem, I tried to put off the recursion call behind the \fi as follows:

\def\recursion#1\nil{%
\ifnum#1>0
\expandafter\firstoftwo%
\else%
\expandafter\secondoftwo%
\fi%
{%
\expandafter\recursion\the\numexpr #1-1\relax\nil%
{#1}%
}{%
{Start}{0}%
}%
}
\def\firstoftwo#1#2{#1}
\def\secondoftwo#1#2{#2}

\edef\result{\recursion 2499\nil}

\show\result %{Start}{0}{1}{2}{3}...'

\bye


To my great surprise this code fails even earlier, namely for initial values greater than 2498.

So, what is going wrong here? How can I solve the problem of stack overflow?

• but the linked question has such a clear and lucid posted answer:-) – David Carlisle Apr 26 '18 at 14:32
• Oh my, I it was you :-) . – AlexG Apr 26 '18 at 14:37
• I guess the overflow is caused by the tokens left behind in the input stream? – AlexG Apr 26 '18 at 14:39
• @AlexG What I said was wrong, sorry. jfbu wrote in a comment what caused the problem :) – Manuel Apr 26 '18 at 15:46
• @AlexG Still, the solution I wrote was basically constructing the sequence from the other end as david has answered. – Manuel Apr 26 '18 at 15:49

To make a tail recursive call you need to build the result token list from the other end:

\def\recursion#1#2{%
\ifnum#1>#2
\expandafter\eatv
\else
{#1}%
\fi
\expandafter\recursion\expandafter{\the\numexpr#1+1\relax}{#2}%
}

\def\eatv#1#2#3#4#5{}

\edef\result{{start}\recursion{0}{7000}} %works up to 4996

\show\result %{Start}{0}{1}{2}{3}...'

\bye

• Once again, a clear and lucid answer :-)! – AlexG Apr 26 '18 at 14:56
• Also nice how you avoid \nil delimited arguments. – AlexG Apr 26 '18 at 14:59
• the great superiority of expl3 shows as it has \use_none:nnnnn ! :) – user4686 Apr 26 '18 at 16:42
• @jfbu : But I would have to \cs_generate_variant:Nn\use_none:nnnnn{NNNnn}, right? – AlexG Apr 26 '18 at 19:31
• @AlexG No need honestly. In your case, if you wanted to optimize more with \exp_after:wN and \q_stop you can use \use_none_delimit_by_q_stop:w .. \q_stop to gobble all that. I mean, if you used the delimited argument for some kind of better performance, if it was not intended, obviously grouped arguments are more standard. – Manuel Apr 26 '18 at 19:32

Speaking slovenly: During recursion don't let your tokens go directly into the input-stack as the input-stack is small. Instead collect them within macro-arguments as the memory for macro-arguments usually is considerably larger.

\def\recursion#1{\innerrecursion{#1}{}}%

\def\innerrecursion#1#2{%
\ifnum#1>0 %
\expandafter\firstoftwo
\else
\expandafter\secondoftwo
\fi
{%
\expandafter\innerrecursion
\expandafter{%
\number\numexpr #1-1\relax}{{#1}#2}%
}{%
{Start}{0}#2%
}%
}
\def\firstoftwo#1#2{#1}
\def\secondoftwo#1#2{#2}

\edef\result{\recursion{5000}}

\show\result %{Start}{0}{1}{2}{3}...'

\bye

• By the way: The gist of my approach is the same as the gist of David Carlisle's approach: Collecting tokens within macro arguments instead of flushing the input stack directly. With my approach the list is not built from whatsoever "other" end. – Ulrich Diez May 15 '18 at 18:46
• \the\numexpr is faster than \number\numexpr. – user4686 May 19 '18 at 10:21
• this approach is f-expandable, however it is much slower than x-expandable code as in David's code (which however requires an \edef to be used, in absence of an \expanded primitive) because it has a cost for TeX to fetch an argument which keeps getting longer. – user4686 May 19 '18 at 10:25

Define suitably \alex_repeat:n:

\input expl3-generic.tex

\ExplSyntaxOn
\cs_new:Npn \recursion #1
{
{Start}{0}
\int_step_function:nnnN { 1 } { 1 } { #1-1 } \alex_repeat:n
}
\cs_new:Npn \alex_repeat:n #1 { {#1} }
\ExplSyntaxOff

\edef\result{\recursion{5000}}

\show\result

\bye