Accumulator and tail recursion #

Tail recursion #

Definition. A function/method is tail-recursive if it is:

• linear recursive, and
• does not perform any operation after a recursive call.

Example. The following function is tail-recursive

-- `True` iff the input string ends with an `s`
endsWithS :: String -> Bool
endsWithS [] = False               -- first base case
endsWithS ['s'] = True             -- second base case
endsWithS (_ : cs) = endsWithS cs  -- inductive case

Example. The function sum seen earlier (and reproduced here) is not tail-recursive, because the addition (Line 3) is performed after termination of the recursive call.

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

Tail recursion elimination (TCE) #

As we have seen earlier, when the function sum is executed, the call stack accumulates stack frames, one per recursive call. Intuitively, each function call (except for the last one) must “wait” for its recursive call to terminate, before resuming its execution.

This is not needed for a tail-recursive function (like endsWith), since no operation is performed after the recursive call.

Accordingly, the Haskell compiler can optimize the execution of such functions, using a single stack frame (the execution becomes similar to that of a loop).

Terminology. This optimization technique is called tail-call elimination (TCE).

Support. Support for TCE varies across programming languages (or compilers):

• many functional languages have compilers that perform TCE: Erlang, F#, Haskell, OCaml, …
• For imperative languages, TCE may:
  • not be performed: Java, …
  • not be guaranteed: Rust, …
  • require explicit annotations: Kotlin, …

Accumulator #

A linear recursive function/method can always be rewritten into a tail-recursive one, by passing it extra argument(s) that carry over computations.

Terminology. These extra arguments are called accumulators.

Warning. Because accumulators are extra input arguments, we need an auxiliary recursive function with a different type (similarly to what we did earlier to return additional values).

Example. The function sum can be implemented in a tail-recursive way, with an accumulator that carries the sum of the values seen so far:

sum :: [Int] -> Int
sum xs = sumRec 0 xs

{-
  Auxiliary function.
  The accumulator `acc` carries the sum of values encountered so far.
-}
sumRec :: Int -> [Int] -> Int
sumRec acc [] = acc -- when reaching the end of the list, return the accumulator
sumRec acc (x : xs) = sumRec (acc + x) xs -- no operation is performed after the recursive call

Hint. Some problems are easier to solve with accumulators (instead of returning additional values).