10

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
  • 1
    @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
8

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
| improve this answer | |
  • Once again, a clear and lucid answer :-)! – AlexG Apr 26 '18 at 14:56
  • 1
    Also nice how you avoid \nil delimited arguments. – AlexG Apr 26 '18 at 14:59
  • 1
    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
  • 1
    @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
3

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
| improve this answer | |
  • 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
2

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
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.