10

For instance, since the following function don't have an accumulator, is it still tail recursive?

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

All the computations in the function are processed before the recursive call, is it a sufficient condition to be considered tail recursive?

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
user1493813
  • 981
  • 1
  • 8
  • 16
  • 1
    Tail recursion is best in strict languages, but in Haskell, things are a little different. [This question](http://stackoverflow.com/questions/13042353/does-haskell-have-tail-recursive-optimization) elicits good information on this issue. – AndrewC Dec 19 '12 at 02:15

2 Answers2

14

Tail recursion does not necessarily need an accumulator. Accumulators are used in tail recursion as a way of communicating a partial result down through the recursive call chain without requiring extra space to be used at each level of the recursion. For example, the canonical tail recursive factorial function needs an accumulator to propagate the partial product built up so far. However, if you don't need to communicate any information from a recursive call down to its subcall, then the accumulator isn't necessary.

The function you've provided is indeed tail recursive, but it doesn't need or use an accumulator. When searching for an element in a list, the recursion doesn't need to remember that all of the elements it has looked at so far aren't equal to the particular element being searched for. It just needs to know what element to look for and what list to search.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

Tail recursion doesn't necessarily need an accumulator. An accumulator is often used, though. Hint, search the wikipedia article for "accumulator".

sjmeverett
  • 1,277
  • 1
  • 11
  • 23