我可以總結我的親身經歷所得出的結論，並附上一個免責聲明，說明後面的內容可能不是完全正確的解釋。謬誤似乎在於Mathematica調用堆棧和傳統調用堆棧之間的差異，Mathematica模式定義的函數實際上是規則。所以，沒有真正的函數調用。 Mathematica需要一個堆棧，原因不同：由於正常評估發生在表達式樹的底部，因此必須保留中間表達式，以防由於規則應用（（子表達式）的某些部分一個表達從底部增長）。特別是，對於定義我們在其他語言中稱爲非尾遞歸函數的規則，情況就是這樣。所以，Mathematica中的堆棧再一次是一堆中間表達式，而不是函數調用。
這意味着，如果作爲規則應用程序的結果，可以整體重寫（子）表達式，則表達式分支不需要保留在表達式堆棧上。這可能是Mathematica中所謂的尾部調用優化 - 這就是爲什麼在這種情況下我們有迭代而不是遞歸（這是規則應用程序和函數調用之間差異的一個很好的例子）。像f[x_]:=f[x+1]這樣的規則屬於這種類型。但是，如果某個子表達式被重寫，產生更多的表達式結構，則表達式必須存儲在堆棧中。規則f[x_ /; x < 5] := (n += 1; f[x + 1])屬於這種類型，直到我們回想起()代表CompoundExpression[]時纔有點隱藏。示意圖這裏發生的是f[1] -> CompoundExpression[n+=1, f[2]] -> CompoundExpression[n+=1,CompoundExpression[n+=1,f[3]]]->etc。儘管每次調用f都是最後一次，但它在執行完整CompoundExpression[]之前發生，所以仍然必須保留在表達式堆棧中。有人可能會爭辯說，這是一個可以優化的地方，爲CompoundExpression制定一個例外，但這可能不容易實現。
現在，來說明我示意上述堆積累的過程，讓我們限制遞歸調用的次數：跟蹤評價
Clear[n, f, ff, fff];
n = 0;
f[x_ /; x < 5] := (n += 1; f[x + 1]);
ff[x_] := Null /; (n += 1; False);
ff[x_ /; x < 5] := ff[x + 1];
fff[x_ /; x < 5] := ce[n += 1, fff[x + 1]];
：
In[57]:= Trace[f[1],f]
Out[57]= {f[1],n+=1;f[1+1],{f[2],n+=1;f[2+1],{f[3],n+=1;f[3+1],{f[4],n+=1;f[4+1]}}}}
In[58]:= Trace[ff[1],ff]
Out[58]= {ff[1],ff[1+1],ff[2],ff[2+1],ff[3],ff[3+1],ff[4],ff[4+1],ff[5]}
In[59]:= Trace[fff[1],fff]
Out[59]= {fff[1],ce[n+=1,fff[1+1]],{fff[2],ce[n+=1,fff[2+1]],{fff[3],ce[n+=1,fff[3+1]],
{fff[4],ce[n+=1,fff[4+1]]}}}}
什麼，你可以看到這是因爲表達式棧積累了f和fff（後者僅用於表明這是一個通用機制，ce[]只是一些任意的頭），但不適用於ff，因爲爲了模式匹配的目的，ff的第一個定義是一個規則嘗試但不匹配的規則，第二個定義完全重寫ff[arg_]，並且不會生成需要進一步重寫的更深的子部分。所以，底線似乎是你應該分析你的函數，看看它的遞歸調用是否會從底部增加評估表達式。如果是的話，就Mathematica而言，它不是尾遞歸的。
如果不顯示如何手動執行尾部呼叫優化，我的回答就不完整。作爲一個例子，讓我們考慮Select的遞歸實現。我們將使用Mathematica鏈接列表來使其合理高效，而不是玩具。下面是對非尾遞歸執行代碼：
Clear[toLinkedList, test, selrecBad, sel, selrec, selTR]
toLinkedList[x_List] := Fold[{#2, #1} &, {}, Reverse[x]];
selrecBad[fst_?test, rest_List] := {fst,If[rest === {}, {}, selrecBad @@ rest]};
selrecBad[fst_, rest_List] := If[rest === {}, {}, selrecBad @@ rest];
sel[x_List, testF_] := Block[{test = testF}, Flatten[selrecBad @@ toLinkedList[x]]]
我用Block和selrecBad是使它更容易使用跟蹤的原因。現在，這個打擊我的機器上的堆棧：
Block[{$RecursionLimit = Infinity}, sel[Range[300000], EvenQ]] // Short // Timing
您可以在小名單追查明白爲什麼：
In[7]:= Trace[sel[Range[5],OddQ],selrecBad]
Out[7]= {{{selrecBad[1,{2,{3,{4,{5,{}}}}}],{1,If[{2,{3,{4,{5,{}}}}}==={},{},[email protected]@{2,{3,{4,
{5,{}}}}}]},{selrecBad[2,{3,{4,{5,{}}}}],If[{3,{4,{5,{}}}}==={},{},[email protected]@{3,{4,{5,
{}}}}],selrecBad[3,{4,{5,{}}}],{3,If[{4,{5,{}}}==={},{},[email protected]@{4,{5,{}}}]},{selrecBad[4,
{5,{}}],If[{5,{}}==={},{},[email protected]@{5,{}}],selrecBad[5,{}],{5,If[{}==={},{},[email protected]@{}]}}}}}}
什麼情況是，結果被累積在列表中越陷越深。該解決方案是不增長的結果表達式的深度，並實現一個方法是讓selrecBad接受一個額外的參數，它是積累的結果（鏈接）名單：
selrec[{fst_?test, rest_List}, accum_List] :=
If[rest === {}, {accum, fst}, selrec[rest, {accum, fst}]];
selrec[{fst_, rest_List}, accum_List] :=
If[rest === {}, accum, selrec[rest, accum]]
並修改主功能因此：
selTR[x_List, testF_] := Block[{test = testF}, Flatten[selrec[toLinkedList[x], {}]]]
這將通過我們的功耗測試就好：
In[14]:= Block[{$IterationLimit= Infinity},selTR[Range[300000],EvenQ]]//Short//Timing
Out[14]= {0.813,{2,4,6,8,10,12,14,16,18,20,
<<149981>>,299984,299986,299988,299990,299992,299994,299996,299998,300000}}
（注意，這裏我們不得不$修改IterationLimit，這是一個好兆頭）。並採用跟蹤揭示了原因：
In[15]:= Trace[selTR[Range[5],OddQ],selrec]
Out[15]= {{{selrec[{1,{2,{3,{4,{5,{}}}}}},{}],If[{2,{3,{4,{5,{}}}}}==={},{{},1},selrec[{2,{3,{4,
{5,{}}}}},{{},1}]],selrec[{2,{3,{4,{5,{}}}}},{{},1}],If[{3,{4,{5,{}}}}==={},{{},1},selrec[{3,
{4,{5,{}}}},{{},1}]],selrec[{3,{4,{5,{}}}},{{},1}],If[{4,{5,{}}}==={},{{{},1},3},selrec[{4,
{5,{}}},{{{},1},3}]],selrec[{4,{5,{}}},{{{},1},3}],If[{5,{}}==={},{{{},1},3},selrec[{5,
{}},{{{},1},3}]],selrec[{5,{}},{{{},1},3}],If[{}==={},{{{{},1},3},5},selrec[{},{{{{},1},3},5}]]}}}
是，這個版本不累加中間表現的深度，因爲結果都保存在一個單獨的列表。
+1非常好的分析。我同意CompoundExpression是優化的候選者，儘管我能夠設計一個子表達式將複合表達式的定義添加到CompoundExpression中，並改變其語義（優化會阻止）。強調「設計」 - 我不確定這在實踐中會成爲問題。 – WReach 2011-01-07 16:44:01
優秀的解釋！現在'$ RecursionLimit'和'$ IterationLimit'之間的區別變得清晰了。什麼是「堆棧」已經變得更加清晰。 – 2011-03-19 07:39:48