尾遞歸是否需要累加器？

Question

例如，由於下面的函數沒有累加器，它仍然是尾遞歸嗎？

belong:: (Ord a) => a -> [a] -> Bool 
belong a [] = False 
belong a (h:t) 
    | a == h = True 
    | otherwise = belong a t 

在函數的所有行運算的遞歸調用之前進行處理，它是要考慮的尾遞歸的充分條件？

Answer 1

尾遞歸不一定需要累加器。累加器在尾遞歸中用作通過遞歸調用鏈向下傳遞部分結果的一種方式，而不需要在遞歸的每個級別使用額外的空間。例如，規範的尾遞歸階乘函數需要一個累加器來傳播目前建立的部分產品。但是，如果您不需要將遞歸調用中的任何信息傳遞給其子調用，則累加器不是必需的。

你提供的函數確實是尾遞歸，但它不需要或使用累加器。在列表中搜索元素時，遞歸不需要記住它迄今爲止查看的所有元素都不等於正在搜索的特定元素。它只需要知道要查找的元素以及要搜索的列表。

希望這會有所幫助！

Answer 2

Tail recursion不一定需要累加器。但是，經常使用累加器。提示，搜索維基百科文章中的「累加器」。