我今天在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"命令运行它们时，两个都有相似的运行时间， normal 递归函数将递减尾巴递归的功能。这与我在LISP中有关尾巴回收优化的信息相反。这样做的原因是什么？
haskell使用懒惰评估来实现递归，因此将任何东西视为在需要时提供值一个thunk）。thunks仅在必要时减少了很多，不再进行。这类似于您从数学上简化表达式的方式，因此以这种方式思考很有帮助。评估顺序不是由您的代码指定的的事实，可以使编译器可以进行很多更聪明的优化，而不是您曾经曾经的尾声淘汰。使用-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函数呼叫挂在周围等待终止 - 每次降低都是应用并消失，留下堆栈框架（这是因为(*)是严格的，因此触发了其第二个论点的评估）。
Haskell的递归功能并未以非常递归的方式评估！唯一徘徊的通话是乘法本身。如果(*)被视为严格的数据构造函数，这就是所谓的守卫递归（尽管通常称其为 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（此处显示为{...}） - 需要一个 extra Space - 描述了未来的计算，要执行的嵌套乘法。
然后，通过将横穿到底部，在堆栈上重新创建计算，从而揭示了此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
编译 - 只有在没有thunk堆积的情况下，尾巴递归才是好的，并且在适当的情况下增加严格性通常有助于防止它。当您建立一个稍后需要的结果时，就会发生这种情况。
- 有时，尾部递归是一个不好的计划，并且保护递归是一个更好的贴合性，即，何时需要一点构建的结果，部分需要一点部分。例如，请参见有关
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可能会在严格分析阶段单独执行此操作。
您应该检查一下Wiki关于Haskell尾递归的文章。特别是由于表达评估，您想要的递归类型是守护递归。如果您详细介绍引擎盖下发生的事情（在Haskell的抽象机器中），您将获得与严格语言的尾部递归相同的东西。随之而来的是，您有一个懒惰功能的统一语法（尾部递归将使您与严格的评估联系在一起，而守卫的递归则更为自然）。
（在学习Haskell中，其余的Wiki页面也很棒！）
如果我没记错的话，GHC会自动优化普通递归函数为尾部恢复优化的功能。