Tail call optimization is a technique used by compilers to optimize the execution of recursive functions. It works by reusing the current stack frame for the next recursive call, instead of creating a new one. This can greatly improve the performance of recursive functions and prevent stack overflow errors.

The key to using tail call optimization is to ensure that the recursive call is the last operation in the function. This is called a tail call. When a function makes a tail call, the current stack frame can be reused for the next call, rather than creating a new one. This way, the stack does not grow indefinitely and the program can avoid stack overflow errors.

Here’s an example of the factorial function with and without tail call optimization:

(* with tail call optimization *)
let rec factorial n =
  if n = 0 then 1
  else n * factorial (n-1)

(* with tail call optimization *)
let rec factorial_tco acc n =
  if n <= 1 then acc
  else factorial_tco (acc * n) (n - 1)

In the tail call optimization example, the function takes two arguments, an accumulator acc and a value n. The base case is when n is less than or equal to 1, in this case the function returns the value of the accumulator. The recursive case is when n is greater than 1, in this case the function makes a tail call by calling itself with the updated values of the accumulator (acc * n) and the decremented value of n (n - 1). This way, the current stack frame can be reused for the next call and the function will not create a new one, avoiding stack overflow errors and improving performance.

Here is another example where a function sum will compute the sum of all numbers up until n:

(* without tail call optimization *)
let rec sum n = 
  if n = 0 then 0
  else n + sum(n - 1)

(* with tail call optimization *)
let rec sum n acc =
  if n = 0 then acc
  else sum (n - 1) (acc + n)

The problem of the solution without tail call optimization becomes clear when tracing sum 5:

sum 5
5 + sum 4
5 + (4 + sum 3)
5 + (4 + (3 + sum 2))
5 + (4 + (3 + (2 + sum 1)))
5 + (4 + (3 + (2 + (1 + sum 0))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

The stack appears in the trace as the nested parentheses. Now imagine calling sum 1000000.

It’s worth noting that not all compilers implement tail call optimization, but OCaml does it by default.

As a recap:

  • Tail call optimization recycles the stack frame of the current function.
  • Only possible when the last step of evaluating a function is to call another function.
  • Very important for recursive algorithms! Enables running in constant stack space.
  • A recursive algorithm that uses only tail calls is called tail-recursive.