☰

如何避免递归期间输入堆栈溢出

tag-icon • tag-icon tex-core expansion recursion
如何避免递归期间输入堆栈溢出

虽然已经有一个↗问题对于类似的标题，我冒险再次提问，因为我认为链接的主题有点臃肿，答案/解决方案太复杂了。

这是一个更通用的例子：

\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

它将结果保存{Start}{0}{1}{2}{3}...{<initial value>}在 中\result。因此，所需的递归宏预计是可扩展的。

在 TeX Live 的默认设置下，上述代码仅适用于初始值不超过 4996 的情况，但其他情况则会失败! TeX capacity exceeded, sorry [input stack size=5000].，可能是由于\ifnum...子句嵌套造成的。

为了解决这个问题，我尝试将递归调用推迟到后面，\fi如下所示：

\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

令我惊讶的是，这段代码甚至更早就失败了，即当初始值大于时2498。

那么，这里出了什么问题？我该如何解决堆栈溢出问题？

答案1

要进行尾部递归调用，您需要从另一端构建结果标记列表：

\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

答案2

说得粗略一点：在递归期间，不要让你的标记直接进入输入堆栈，因为输入堆栈很小。相反，将它们收集在宏参数中，因为宏参数的内存通常要大得多。

\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

答案3

适当定义\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

相关内容