What is tail recursion?

Tail recursion

The tail recursion function does not compute anything useful after a recursive call ends; instead, it’s used in its true form to keep track of how many times to call and not be a part of successive computations.

Non-tail recursive factorial function

// Non Tail Recursive factorial
unsigned long long int factorial (unsigned int x) {
	return x > 0 ? x * factorial(x - 1) : 1;
}

This function is not tail-recursive since the multiplication happens after the function returns from a recursive call. The recursion is a part of the computation. Below is the memory usage footprint for the non-tail optimized function.

  ...
	Maximum resident set size (kbytes): 10480
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 1891
  ...

Tail recursive factorial function

// tail recursive version
void tail_factorial (unsigned int x, unsigned int* acc) {
	if (x > 0) {
		*acc = *acc * x;
		tail_factorial(x - 1, acc);
	} else {
		return;
	}
}

This is a tail-recursive. Notice the difference here. The recursive function call is just a tracker of how many times to recurse, not a part of the actual multiplication. No computation work is done after the function returns, so modern compilers optimize that to keep just one frame for the function call instead of a whole recursive stack.

  ...
  	Maximum resident set size (kbytes): 7968
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 1300
  ...

It also has a smaller memory footprint.