Tail Recursion

A tail call is when the callee’s result is merely returned without being used (i.e. it is not multiplied or added to anything, etc).

In tail call optimization, the caller pops before the actual call to reuse the stack. This way you do not get stack overflow.

The typical pattern for tail recursion is to have the helper function pass in an accumulator. The old base case becomes the initial accumulator. The new case becomes the final value of the accumulator. Your helper function returns the accumulator.

Example:

fun rev2 lst =
  let fun aux (lst, acc) =
     case lst of
         [] => acc
       | x::xs' => aux(xs, x::acc)
  in
     aux(lst, [])
  end

Note: The tail call need not be to the same function!