Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

c++
tail recursion
optimization
community creator

What is tail recursion?

Sumit Lahiri

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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

#include <iostream>
using namespace std;
// Non Tail Recursive factorial
unsigned long long int factorial (unsigned int x) {
return x > 0 ? x * factorial(x - 1) : 1;
}
int main() {
cout << factorial(5);
}
// 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

#include <iostream>
using namespace std;
// Tail recursive version
unsigned long long int tail_factorial (unsigned int x, unsigned int* acc) {
if (x > 0) {
*acc = *acc * x;
tail_factorial(x - 1, acc);
} else {
return *acc;
}
}
int main() {
unsigned int a = 1;
cout << tail_factorial(5, &a);
}
// 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.

RELATED TAGS

c++
tail recursion
optimization
community creator

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring