whenever there is pending operation to be performedthe function becomes non-tail recursive in such non-tail recursive functioninformation about each pending operation must be storedso the amount of information directly depends on the number of calls howeverthe same factorial function can be written in tailrecursive manner as shown fig in the codefact function preserves the syntax of fact(nhere the recursion occurs in the fact function and not in fact function carefully observe that fact has no pending operation to be performed on return from recursive calls the value computed by figure tail recursion the recursive call is simply returned without any modification so in this casethe amount of information to be stored on the system stack is constant (only the values of and res need to be storedand is independent of the number of recursive calls int fact(nreturn fact ( )int fact (int nint resif ( = return reselse return fact ( - *res)converting recursive functions to tail recursive non-tail recursive function can be converted into tail-recursive function by using an auxiliary parameter as we did in case of the factorial function the auxiliary parameter is used to form the result when we use such parameterthe pending operation is incorporated into the auxiliary parameter so that the recursive call no longer has pending operation we generally use an auxiliary function while using the auxiliary parameter this is done to keep the syntax clean and to hide the fact that auxiliary parameters are needed linear and tree recursion int fibonacci(int numif(num =return else if (num = return else return (fibonacci(num fibonacci(num ))observe the series of function calls when the function returnsthe pending operations in turn calls the function fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( now we havefibonacci( fibonacci( fibonacci( fibonacci( fibonacci( fibonacci( figure tree recursion recursive functions can also be characterized depending on the way in which the recursion grows in linear fashion or forming tree structure (fig in simple wordsa recursive function is said to be linearly recursive when the pending operation (if anydoes not make another recursive call to the function for exampleobserve the last line of recursive factorial function the factorial function is linearly recursive as the pending operation involves only multiplication to be performed and does not involve another recursive call to fact on the contrarya recursive function is said to be tree recursive (or non-linearly recursiveif the pending operation makes another recursive call to the function for examplethe fibonacci function in which the pending operations recursively call the fib onacci function tower of hanoi the tower of hanoi is one of the main applications of recursion it says'if you can solve - casesthen you can easily solve the nth case