☰

在 LaTeX3 中使用递归

tag-icon • tag-icon expl3
在 LaTeX3 中使用递归

我想在LaTeX3中使用递归计算n！，但发现结果不正确，mwe如下

\documentclass{article}                          
\ExplSyntaxOn
\cs_set:Nn \froac:n {
\int_compare:nNnTF{#1}={0}{1}
{
     \int_eval:n{#1*\froac:n{#1-1}}
}
}
\ExplSyntaxOff
\begin{document}
\ExplSyntaxOn
\froac:n{4}
\ExplSyntaxOff
\end{document}

谢谢你！

答案1

请记住，TeX 是一种宏语言。让我们手动展开递归的两个步骤来看看发生了什么：

你开始

\froac:n{4}

由于 4 不为 0，因此

\int_eval:n{4*\froac:n{4-1}}

现在4-1仍然不是0，所以下一个迭代步骤导致

\int_eval:n{4*\int_eval:n{4-1*\froac:n{4-1-1}}}

当然4-1*\froac:n{4-1-1}不是你想要的。你可以通过添加括号来解决这个问题：

\documentclass{article}                          
\ExplSyntaxOn
\cs_set:Nn \froac:n {
\int_compare:nNnTF{#1}={0}{1}
{
     \int_eval:n{(#1)*\froac:n{(#1)-1}}
}
}
\ExplSyntaxOff
\begin{document}
\ExplSyntaxOn
\froac:n{4}
\ExplSyntaxOff
\end{document}

答案2

只是为了多样性，这里有一个基于 LuaLaTeX 的解决方案。

在此处输入图片描述

函数froac会产生溢出n>20。虽然n>20这似乎是一个相当差的溢出阈值，但请注意\froac:n(a) @MarcelKrüger 的回答和（b）@UlrichDiez 的回答两者都具有更为严格的溢出阈值：n>12。

\documentclass{article}
\directlua{ 
   %% Define a Lua function called 'froac'

   function froac ( n )
      if n==0 or n==1 then return 1 
      else return n * froac ( n-1 )
      end
   end 

}
%% Define a LaTeX wrapper macro called '\froac'
\newcommand\froac[1]{\directlua{tex.sprint(froac(#1))}}

\begin{document}

$\begin{array}{rr}
\directlua { for i = 0 , 20 do 
                tex.sprint ( i .. "&" .. froac ( i ) .. "\\\\" )  
             end }
\end{array}$

\end{document}

附录/备注：尽管阶乘函数的通常定义（即递归定义）倒计时从n到0（或1），从计算上来说，实际上更有效的是计数到n。这样做使我们能够if n==0在例程开始时仅评估一次条件，然后for对整数范围执行确定性循环。在 Lua 中，这个想法可以按如下方式实现：

-- Define 'froac' by counting _up_ rather than down
function froac(n)
   if n==0 or n==1 then return 1 
   else f=2; for i=3,n do f=f*i end; return f 
   end
end

答案3

\bigintcalcFac包的bigintcalc可以计算大于 12 的数字的阶乘，但这不是解释。;-)

expl3\fp_eval:n { fact( <number> ) }是更可取的，因为它的速度更快，并且算术溢出的处理也更好。

通过递归调用累积嵌套调用\int_eval和属于这些调用的标记\froac可能会触发 TeX 容量超出错误。这在这里并不重要，因为还面临算术溢出的问题。

尽管如此，为了在 expl3 中使用扩展玩得开心，以下变体不会累积对 的嵌套调用\int_eval。
但它需要\exp_args:Nff在 2018-05-15 引入。
当尝试计算大于 12 的数字的阶乘时，会出现算术溢出。（与 相同\number\numexpr 1*2*3*4*5*6*7*8*9*10*11*12\relax。\number\numexpr 1*2*3*4*5*6*7*8*9*10*11*12*13\relax）

\documentclass{article}                          
\ExplSyntaxOn
\cs_set:Nn \froac:n {
  \exp:w \int_compare:nNnTF{#1}>{1}{\exp_args:Nf\froacstep:nn{\int_eval:n{#1}}{#1}}{\exp_end: 1}
}
\cs_set:Nn\froacstep:nn{
   % #1 result calculated so far
   % #2 factor in the previous iteration
   \int_compare:nNnTF{#2}>{2}{
     \exp_args:Nff\froacstep:nn
                  {\int_eval:n{(#1)*((#2)-1)}}
                  {\int_eval:n{(#2)-1}}
   }{ \exp_end: #1 }
}
\ExplSyntaxOff
\begin{document}
\ExplSyntaxOn
\froac:n{12}\par
\froac:n{5}\par
\froac:n{4}\par
\froac:n{3}\par
\froac:n{2}\par
\froac:n{1}\par
\froac:n{0}
\ExplSyntaxOff
\end{document}

在此处输入图片描述

答案4

这是一个阶乘函数，用functional包。这不是最简短的答案，但它非常直观，因为这个包在Lua语言中模拟了函数式编程。函数的评估是从内到外的。

-- lua code for comparison --
-- define a function --
function Fact (n)
  if n == 0 then
    return 1
  else
    return n * Fact(n-1)
  end
end
-- use the function --
print(Fact(4))

\documentclass{article}
\usepackage{functional}
\Functional{scoping=true} % make every function become a group
\begin{document}

\IgnoreSpacesOn
\PrgNewFunction \Fact { m } {
  \IntCompareTF {#1} = {0} {
    \Result {1}
  }{
    \Result {\IntMathMult{#1}{\Fact{\IntEval{#1-1}}}}
  }
}
\IgnoreSpacesOff
\Fact{4}

\end{document}

请注意，使用此包，您需要通过\Result命令传递函数的返回值。

相关内容