Problem 4 10pt Consider the following implementation in the

Problem 4 [10pt] Consider the following implementation in the C language:

int g(int x) {

if (x == 1) {

return 1;

}

return x*g(x-1);

}

a) (6pt) Write down a tail recursive implementation of function g. You can use helper function in your solution.

b) (4pt) 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

a)
A recursive function is tail recursive when last statement of function is recursive call.

Tail Recursive Function :

int g(int x, int returnValue=1){
if(x==1){
return returnValue;
}
else{
return g(x-1, returnValue*x);
}
}

Explanation :

//pass the values 4 and 1 to the function

g(4,1)
return g(3, 1 * 4 ) //x == 4
return g(2, 4 *3 ) //x== 3
return g(1, 12 *2 ) //x == 2
return 24 // when x == 1 it returns 24 and exits the function

b)