如何制作尾递归函数

Question

我真的对如何使函数“尾递归”感到困惑。

这是我的函数，但我不知道它是否已经是尾递归。

我正在尝试在Haskell中合并两个列表。

merge2 :: Ord a =>[a]->[a]->[a]
merge2 xs [] = xs
merge2 [] ys = ys
merge2 (x:xs)(y:ys) = if y < x then y: merge2 (x:xs) ys else x :merge2 xs (y:ys)

Answer 1

您的函数不是尾递归的；它是受保护的递归。但是，如果要提高内存效率，则应在Haskell中使用受保护的递归。

为了使调用成为尾部调用，其结果必须是整个函数的结果。此定义适用于递归和非递归调用。

例如，在代码中

f x y z = (x ++ y) ++ z

该调用(x ++ y) ++ z为尾调用，因为其结果是整个函数的结果。呼叫x ++ y是不是尾调用。

有关尾递归的示例，请考虑foldl：

foldl :: (b -> a -> b) -> b -> [a] -> b
foldl _ acc []     = acc
foldl f acc (x:xs) = foldl f (f acc x) xs

递归调用foldl f (f acc x) xs是尾递归调用，因为它的结果是整个函数的结果。因此，这是一个尾部调用，并且是foldl对自身的调用是递归的。

代码中的递归调用

merge2 (x:xs) (y:ys) = if y < x then y : merge2 (x:xs) ys 
                                else x : merge2 xs (y:ys)

不是尾递归的，因为它们没有给出整个函数的结果。调用的结果将merge2用作整个返回值（新列表）的一部分。该(:)构造函数，而不是递归调用，给出整个函数的结果。实际上，懒惰会立即(:) _ _返回，并且_只有在需要时和以后才填充漏洞。这就是为什么有保护的递归节省空间的原因。

但是，尾部递归不能保证惰性语言的空间效率。通过惰性评估，Haskell可以在内存中建立thunk或结构，以表示尚待评估的代码。考虑以下代码的评估：

foldl f 0 (1:2:3:[])
=> foldl f (f 0 1) (2:3:[])
=> foldl f (f (f 0 1) 2) (3:[])
=> foldl f (f (f (f 0 1) 2) 3) []
=> f (f (f 0 1) 2) 3

您可以认为惰性评估是“从内而外”发生的。foldl评估对的递归调用时，将在累加器中建立重击。因此，由于延迟的计算，使用累加器进行尾部递归在惰性语言中的空间效率不高（除非在下一次进行尾部递归调用之前立即将累加器强制执行，从而防止了thunk堆积并呈现已经-计算值，最后）。

而不是尾部递归，您应该尝试使用受保护的递归，其中递归调用隐藏在惰性数据构造函数中。使用惰性评估时，将评估表达式，直到它们处于弱头正常形式（WHNF）。表达式在WHNF中时为：

考虑map：

map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

map (+1) (1:2:3:[])
=> (+1) 1 : map (+1) (2:3:[])

(+1) 1 : map (+1) (2:3:[])由于(:)数据构造函数的原因，该表达式位于WHNF中，因此评估在此时停止。您的merge2函数还使用受保护的递归，因此在惰性语言中它也节省了空间。

TL; DR：在一种懒惰的语言中，如果尾部递归在累加器中累积了重击，则尾递归仍会占用内存，而受保护的递归不会累积重击。

有用的网址：