Tail Recursion

We have already seen tail recursion in previous examples:

void fun(int n) {
  if (n > 0) {
    printf("%d", n);
    fun(n - 1);
  }
}

fun(3);

If a function is calling itself, and the recursive call is the last statement in that function, then it is called a tail recursion (since after that call, it is not doing anything else).

All the operations will be performed at calling time only, and the function will not be performing any operation at a returning time.

Any recursive function can be written as a loop, and vice versa. The time taken in both cases would be O(n). But the space complexity for recursion is O(n), while for the loop, it will be O(1).

Loops will be more efficient than tail recursion, but that will not be true for every type of recursion. The compiler will try to optimize tail recursions into a loop though to reduce the space consumption.

void fun(int n) {
  while (n > 0) {
    printf("%d", n);
    n--;
  }
}