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.
#include <iostream>using namespace std;// Non Tail Recursive factorialunsigned 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
...
#include <iostream>using namespace std;// Tail recursive versionunsigned 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.