在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中，爲什麼遞歸函數中的替換不會終止？

回答

相關問題