在Mathematica中，为什么递归函数中的替换不会终止？

想象我在数学定义的递归阶乘，像这样：在Mathematica中，为什么递归函数中的替换不会终止？

Clear[fact] 
fact[0] = 1 
fact[n_] := n fact[n - 1]

评估事实[10]确认功能的工作原理和终止。

一个主要的例子，但它在这个问题上的目的。实际上，我的问题一般都是关于递归函数定义的。

我的预期评估以下替换终止，以及：

x fact[x-1] /. x -> 2

唉，在一个递归深度限制运行：

$RecursionLimit::reclim: Recursion depth of 256 exceeded.

我希望看到这样的：

2 fact[2-1]

或只是值

UPDATE：的其实另一种递归定义确实按预期方式工作：

Clear[fact] 
fact[n_] := If[n < 1, 1, n fact[n - 1]]

但这一事实（双关语意;-)使得它更神秘的对我说：为什么它表现如此不同？

我的问题是双重的：

即使有内置的帮助和搜索网为线索，我无法解释为什么数学在坚持，很显然，保持象征性的结果，而不是评估'中间'结果并很好地结束。谁冒险一个可行的解释？
我该如何说服Mathematica根据我的期望执行（除了使用的替代方案，如果 []）？

我真的很困惑这个，我真的希望有人能帮助我。

/M炼

来源

2011-11-19 nanitous

试图u[x_] := x; Trace[x*u[x] /. x -> 2]，它首先评估x和u[x]。在你的情况下，它首先尝试评估fact[x-1]，然后将x替换为2，并达到递归限制。

Attributes[ReplaceAll]表明它没有属性HoldFirst，所以它首先评估它的第一个参数。例如，

[email protected][Hold[x*fact[x - 1]], x -> 2]

给出的预期2，因为它拥有的第一个参数，替换，然后释放保持，因为你预期。

另一种方式来做到这一点是

Unprotect[ReplaceAll] 
SetAttributes[ReplaceAll, HoldFirst] 
ReplaceAll[x*fact[x - 1], x -> 2]

，但不这样做。

虽然有人会尽快给出更好的解释。

编辑：在响应于所述添加问题，即为什么

Clear[factif] 
factif[n_] := If[n < 1, 1, n factif[n - 1]]

不会导致无限递归：以这种方式定义，factif[x]计算结果为If[x < 1, 1, x factif[x - 1]]，由于x<1不能评价。因此，它的ReplaceAll第一个参数的评估未遂后仍保留在这种形式下，则会发生置换等

来源

2011-11-19 02:50:35 acl

Aha，这很有道理：Mathematica首先评估/的LHS。然后_then_执行替换。通过Hold []，您可以推迟“渴望”的评估。感谢您的杰出答案：有效，相关，清晰和简洁！我的赞美 – nanitous

@nanitous干杯！如果三个答案中的一个能够回答您的问题，您可以将其标记为已接受的答案，以便它出现在顶部（并为答案者提供声望提升）。 – acl

谢谢指出！ – nanitous

这是因为你正在评估此：更换发生

fact[x-1]

之前。只要做fact[x-1]，你会得到错误。

您可以修复你的fact功能，像这样：

Clear[fact] 
fact[0] = 1 
fact[n_Integer?Positive] := n fact[n - 1]

然后x fact[x - 1] /. x -> 2回报2这似乎是正确的。

请记住，您的函数参数模式fact[n_]是极其一般。例如，它允许像fact[Integrate[Sin[x], x]]这样的东西进行评估，这可能不是你想要的。使用fact[n_Integer]更精确，并且允许fact函数以您希望的方式工作。

如果你想更好地定义这个功能，你可以这样做：

Clear[fact] 
fact::nicetrybuddy = "fact[``] is not defined."; 
fact[0] = 1 
fact[n_Integer?Positive] := n fact[n - 1] 
fact[n_] := (Message[fact::nicetrybuddy, n]; $Failed)

这样类似fact["x"]将失败，一个消息：

fact::nicetrybuddy: fact[x] is not defined.

来源

2011-11-19 02:51:23

好主意添加一个全面的条款！我必须记住那一个。 – nanitous

其他的答案是正确的：fact在其参数被替换之前进行评估。基本问题是，您已经在头脑中定义了fact整数输入，并且没有为非整数输入提供终端条件。如果你不是做

Clear[fact] 
fact[0] = 1 
fact[n_Integer?Positive] := n fact[n - 1]

然后fact将留下不计算，直到它有一些相匹配的正整数。

您可能需要将替换语句包装在Evaluate中，然后在替换参数后触发fact的定义。

另一种方法可能是使用一个纯函数：

# fact[#-1]& @ 2

这不应该过早地评估。

来源

2011-11-19 02:57:14 Verbeia

我现在正在运行一个大型模拟（400,000 Hodrick-Prescott过滤器！），所以我没有用纯函数检查最后的建议。 – Verbeia

我考虑过这个。但我已经尝试了不同的递归函数，例如为列表。我遇到了同样的行为。所以我尽可能地将这个问题发布了。但是，一个例子再次使事情变得具体。对不起。 – nanitous

在Mathematica中，为什么递归函数中的替换不会终止？

回答

相关问题