Tail Recursive

Overview

Tail recursion is a specific form of recursion where the recursive call is the last operation performed in a function. This characteristic allows for a significant optimization known as tail call elimination (TCE). In languages that support TCE, the compiler or interpreter can optimize tail recursive functions by transforming them into iterative loops. This transformation is crucial for implementing stack-safe recursive methods, as it prevents stack overflow by reusing the current function's stack frame for the next function call.

Example

A classic example of a tail recursive method is the sumTail function, which calculates the sum of a list of integers. In this function, the recursive call to sumTail is the last operation performed, making it a candidate for tail call optimization:

static Integer sumTail(List<Integer> list, int acc) {
  return list.isEmpty()
      ? acc
      : sumTail(tail(list), acc + head(list));
}

In this example, sumTail takes a list of integers and an accumulator acc. If the list is empty, it returns the accumulated sum. Otherwise, it recursively calls itself with the tail of the list and the updated accumulator, which includes the head of the list.

Figure

Listing 4.4. A standalone tail recursive function Listing 4.4. A standalone tail recursive function

This figure illustrates a standalone tail recursive function, showcasing the structure and flow of a typical tail recursive implementation.