Consider the following implementation in the C language int

Consider the following implementation in the C language: int g(int x) {if (x == 1) {return 1;} return x*g(x-1); Write down a tail recursive implementation of function g. You can use helper function in your solution. An \"optimizing\" compiler will often be able to generate efficient code for recursive functions when they are tail-recursive. Refer to activation record, briefly explain how a compiler may \"reuse\" the same activation record for your solution in a).

Solution

#include<iostream>
using namespace std;

// A tail recursive function to calculate factorial
int g( int x, int a)
{
   if (x == 0) return a;

   return g(x-1, x*a);
}

// A wrapper over factTR
int fact( int x)
{
return g(x, 1);
}

// Driver program to test above function
int main()
{
   cout << fact(5);
   return 0;
}

======================================================

b)What is tail recursion?
A recursive function is tail recursive when recursive call is the last thing executed by the function. For example the following C++ function print() is tail recursive.

Why do we care?
The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler. The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use

Can a non-tail recursive function be written as tail-recursive to optimize it?
Consider the given function to calculate factorial of n. It is a non-tail-recursive function. Although it looks like a tail recursive at first look. If we take a closer look, we can see that the value returned by g(n-1) is used in g(n), so the call to g(n-1) is not the last thing done by g(n)

It can be written as a tail recursive function. The idea is to use one more argument and accumulate the factorial value in second argument. When n reaches 0, return the accumulated value.