Skip to content

Tail Recursion

A function is tail recursive when the recursive call is the last function invoked in the evaluation of the body of the function. We don't need to return to the caller at all.

Normal recursion: You need to stack to remember what "remains to be computed". Tail recursion: You need to remember nothing.

Tail recursion is comparable with iteration.

Haskell example

Naive recursion

sumList :: [Int] -> Int
sumList [] = 0
sumList (x:xs) = x + (sumList xs)

Tail recursion

sumList' :: [Int] -> Int
sumList' xs = sumLoop 0 xs
  where
    sumLoop n []      = n
    sumLoop n (x:xs)  = sumLoop (n + x) xs

References


Last update: November 23, 2020