Let the function do no work after it returns on finishing a subsequent recursive call. By that we mean, the function does not compute anything usefull after a recursive call ends. The recursion is used in it's true form to just keep track of how many times to call and not be a part of successive computations.
// 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 foot print for the non-tail optimised 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 version
void tail_factorial (unsigned int x, unsigned long long 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 cpus actually optimise that to keep just one frame for the function call and not 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
...Lesser memory footprint.