今天我在Unix中发现了"time"命令，想用它来检查Haskell中尾递归和普通递归函数运行时间的差异。
我编写了以下函数：
--tail recursive
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
fac' 1 y = y
fac' x y = fac' (x-1) (x*y)
--normal recursive
facSlow :: (Integral a) => a -> a
facSlow 1 = 1
facSlow x = x * facSlow (x-1)
考虑到这些代码仅供此项目使用，因此我没有检查零或负数是否有效。
然而，在为每个函数编写主方法、编译它们并使用“time”命令运行它们后，两个函数的运行时间相似，其中普通递归函数略优于尾递归函数。这与我听说的关于lisp中尾递归优化的情况相反。原因何在？
Haskell使用惰性求值来实现递归，因此将任何东西视为在需要时提供值的承诺（这称为thunk）。Thunk仅在必要时被减少到足以继续进行的程度，不再多。这类似于你数学上简化表达式的方式，因此思考这种方法是有帮助的。由于评估顺序未由您的代码指定，因此编译器可以执行许多比您习惯的尾调用消除更聪明的优化。 如果您想进行优化，请使用-O2进行编译！
让我们以facSlow 5作为案例研究来看看如何评估：
facSlow 5
5 * facSlow 4 -- Note that the `5-1` only got evaluated to 4
5 * (4 * facSlow 3) -- because it has to be checked against 1 to see
5 * (4 * (3 * facSlow 2)) -- which definition of `facSlow` to apply.
5 * (4 * (3 * (2 * facSlow 1)))
5 * (4 * (3 * (2 * 1)))
5 * (4 * (3 * 2))
5 * (4 * 6)
5 * 24
120
所以就像你担心的那样，在进行任何计算之前，我们会有一系列数字的积累，但与你担心的不同的是，没有等待终止的facSlow函数调用堆栈-每个缩减都会被应用并消失，留下一个堆栈帧（这是因为(*)是strict的，因此会触发其第二个参数的求值）。
Haskell的递归函数并不是以非常递归的方式进行评估！挂起的调用堆栈只有乘法本身。如果将(*)视为严格数据构造函数，则被称为guarded递归（尽管通常是指具有non-strict数据构造函数的情况，其中留下的是数据构造函数 - 当进一步访问时强制执行）。
现在让我们看一下尾递归的fac 5：
fac 5
fac' 5 1
fac' 4 {5*1} -- Note that the `5-1` only got evaluated to 4
fac' 3 {4*{5*1}} -- because it has to be checked against 1 to see
fac' 2 {3*{4*{5*1}}} -- which definition of `fac'` to apply.
fac' 1 {2*{3*{4*{5*1}}}}
{2*{3*{4*{5*1}}}} -- the thunk "{...}"
(2*{3*{4*{5*1}}}) -- is retraced
(2*(3*{4*{5*1}})) -- to create
(2*(3*(4*{5*1}))) -- the computation
(2*(3*(4*(5*1)))) -- on the stack
(2*(3*(4*5)))
(2*(3*20))
(2*60)
120
因此您可以看到，仅靠尾递归本身并没有节省任何时间或空间。它不仅总步数比facSlow 5更多，而且还构建了一个嵌套的thunk（在这里显示为{...}）-需要额外的空间-其中描述了未来的计算，即要执行的嵌套乘法。
然后通过遍历它来展开这个thunk，将其重新创建在栈上进行计算。对于两个版本都存在使用非常长的计算时可能导致堆栈溢出的风险。
如果我们想要手动优化它，我们所需做的就是使其严格。您可以使用严格应用程序运算符$!来定义。
facSlim :: (Integral a) => a -> a
facSlim x = facS' x 1 where
facS' 1 y = y
facS' x y = facS' (x-1) $! (x*y)
这迫使facS'在其第二个参数中是严格的。(因为必须评估第一个参数才能决定应用哪个facS'定义，所以它已经对第一个参数严格了。)
有时候严格性可以极大地帮助，有时候却是个大错误，因为惰性更有效率。在这里使用严格性是一个好主意：
facSlim 5
facS' 5 1
facS' 4 5
facS' 3 20
facS' 2 60
facS' 1 120
120
我想这就是你想要实现的。
-O2编译。foldr和foldl的此问题，并将它们相互测试。试试这两个：
length $ foldl1 (++) $ replicate 1000
"The size of intermediate expressions is more important than tail recursion."
length $ foldr1 (++) $ replicate 1000
"The number of reductions performed is more important than tail recursion!!!"
foldl1 是尾递归的，而 foldr1 则执行受保护的递归，以便第一个项立即呈现以进行更进一步的处理/访问。（第一个"括号"一次向左，(...((s+s)+s)+...)+s，迫使它的输入列表完全达到其末尾并构建了一个未来计算的大块，远早于需要其全部结果；第二个则逐渐向右括号，s+(s+(...+(s+s)...))，一点一点地消耗输入列表，因此整个过程能够在常量空间中运行，并具有优化）。
根据所使用的硬件，您可能需要调整零的数量。
需要提到的是，fac函数并不适合使用保护递归。这里应该使用尾递归。由于惰性求值，在fac'函数中你没有得到TCO的效果，因为累加器参数会构建大量的thunk，当它们被评估时将需要一个巨大的堆栈。为了防止这种情况并获得所需的TCO效果，您需要使这些累加器参数强制求值。
{-# LANGUAGE BangPatterns #-}
fac :: (Integral a) => a -> a
fac x = fac' x 1 where
fac' 1 y = y
fac' x !y = fac' (x-1) (x*y)
如果您使用-O2（或仅使用-O）进行编译，则GHC很可能会在严格性分析阶段自行执行此操作。
$!比BangPatterns更清晰，但这是一个很好的答案。特别是提到了严格性分析。 - singpolyma（在学习Haskell时，维基百科上的其他页面也很棒！）
如果我没记错的话，GHC会自动将普通递归函数优化为尾递归优化函数。
fac函数与 ghc 使用辅助函数prod计算product [n,n-1..1]的方式几乎相同，但当然product [1..n]更简单。我只能假设他们没有在第二个参数中强制执行严格性，因为 ghc 很自信它可以将其编译成一个简单的累加器。 - AndrewC