尾递归和保护递归有什么区别？

Question

在我的练习中，我必须决定函数是什么类型的递归。

我们必须从线性递归、尾递归和保护递归中进行选择，但我不太明白后两者之间的区别。

有人可以解释一下保护递归和尾递归之间的区别吗？

我们要区分的功能供参考：

pow2 0 = 1
pow2 n = 2 * pow2 (n-1)

factAux r i n
  | i <= n = factAux (i * r) (i + 1) n | otherwise = r
factorial = factAux 1 1

init [x] = []
init (x:xs) =  x : init xs

binom n 0 = 1
binom n k
  | n == k = 1
  | otherwise = binom (n - 1) k + binom (n - 1) (k - 1)

negList [] = []
negList (x : xs) = if x > 0 then negList (-x : xs) else x : negList xs

Answer 1

我不会解决你的家庭作业，因为这会适得其反。

相反，我将回答帖子标题中的问题：

尾递归

当以下情况时，调用是尾递归的：

• 这是递归的
• 该调用的结果立即返回，之后不进行任何修改或操作

例如：

-- This is tail-rec
f x = if x == 0
      then 0
      else f (x + 1)

-- This is not
g x = if x == 0
      then 0
      else g (x + 1) - 1

-- And this is not too
h x = h (h x)

有关更多信息，请查看此线程。

保护递归

当递归调用位于数据构造函数的惰性参数下时，会发生这种情况：

-- This is guarded-rec
f x = if x == 0
      then []
      else x : f (x - 1)  -- (:) is lazy on both operands

-- And this is not
g x = if x == 0
      then []
      else g (x - 1)

-- And this is not too
data StrictList a = SNil | SCons !a !(StrictList a)
h x = if x == 0
      then SNil
      SCons x (h x)

交叉示例

此链接可能会帮助您了解其中的差异。另请查看this，尽管它在 Prolog 中给出了示例。

尾部记录和护卫记录

这是矛盾的，因为用构造函数保护递归调用破坏了尾递归的“对结果不做任何事情”的要求。

尾部记录而不是保护记录

f x = f x

不是尾部记录和保护记录

f x = x : f x

不是尾部记录，也不是保护记录

f x = f x + 1