我对如何使函数“尾递归”感到非常困惑。
这是我的函数，但是我不知道它是否已经是尾递归。
我正在尝试合并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)
您的函数不是尾递归的；它是受保护的递归。但是，如果要提高内存效率，应该在Haskell中使用保护的递归。
要成为尾部调用，其结果必须是整个函数的结果。此定义适用于递归和非递归调用。
例如，在代码中
f x y z = (x ++ y) ++ z
调用(x ++ y) ++ z是尾部调用，因为其结果是整个函数的结果。呼叫x ++ y是not尾呼叫。
关于尾递归的示例，请考虑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是尾递归调用，因为其结果是整个函数的结果。
代码中的递归调用
merge2 (x:xs)(y:ys) = if y < x then y: merge2 (x:xs) ys else x :merge2 xs (y:ys)
不是尾递归的，因为它们没有给出整个函数的结果。调用merge2之后，您将获取结果并将其用于构造新列表。 (:)构造函数（而不是递归调用）提供整个函数的结果。
但是，尾部递归不能保证惰性语言的空间效率。通过惰性评估，Haskell可以在内存中建立thunks或表示尚未评估代码的结构。考虑以下代码的评估：
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的递归调用时，将在累加器中建立重击。因此，由于延迟评估，使用累加器进行尾递归在惰性语言中的空间效率不高。
而不是尾部递归，您应该尝试使用受保护的递归，其中递归调用隐藏在数据构造函数中。使用惰性评估时，将评估表达式，直到它们为弱头正常形式（WHNF）。表达式位于WHNF中时，可以是：
Just (1 + 1)）const 2）\x -> x）考虑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：在一种懒惰的语言中，如果尾递归在累加器中堆积了thunk，则尾递归仍会占用内存，而受保护的递归不会堆积thunk。
有用的链接：