Tail Recursion: Concept and examples of converting recursive problems to tail-recursive forms

Photo by Reid Zura on Unsplash

What is a tail recursive function?

A tail recursive function is a function that invokes itself at the end of the function. For example:

// Tail recursive function
public void print_int_1(int n) {
  if (n == 0)
    return;
  
  System.out.println(n);
  print_int(n-1);
}

Tail-recursive functions are preferable to non-tail-recursive functions because they can be optimized by modern compilers. This is because, when the recursive call is the last thing executed by the function, it is unnecessary to save the state of the current recursive function’s stack frame.

When a compiler recognizes that the recursive call is the last statement of the function, it can eliminate the recursive call, transforming the recursive function into a non-recursive function. This optimization reduces the function’s space complexity from O(n) to O(1) auxiliary space.

public void print_int_1(int n) {
  // start:
  if (n == 0)
    return;
  
  System.out.println(n);
  print_int(n-1); // This line will be replaced with the following two lines
                  // n = n - 1
                  // go to start
}