CODEWITHSUNDEEP
c++recursion
venaizu
venaizu

Reputation: 25

How to apply Tail Call optimization

I have written a recursive function, but the recursion takes a lot of time when I enter a big number, such as 100.

I want to apply tail call optimization in the code, to minimize the computation time, but I am not able to do it.

The recursive algorithm is f(n) = f(n-1) + f(n-2)

int fib(int n)
{
    if (n == 1) return n;
    if (n == 0) return n;
    return fib(n - 1) + fib(n - 2);
}

int _tmain(int argc, _TCHAR* argv[])
{
    std::cout << "---->" << fib(3);
    std::system("PAUSE");
    return 0;
}

Upvotes: 0

Views: 716

Answers (2)

Remy Lebeau
Remy Lebeau

Reputation: 595320

Tail Call Optimization (TCO) only works when the last instruction of the function immediately returns the output of another function call (which can be a recursive call). But that is not the case in this situation.

The whole purpose of TCO is to allow the compiler to make constant usage of stack space through multiple function calls. IOW, the compiler can allocate a single stack frame (if any) and reuse it over and over without messing anything up.

Your fac() function is calling itself twice, adding the return values together, and then returning the result of the addition to the caller. As such, local temp variables are created to receive those return values. Each function call has to create a new stack frame to hold its own local variables, which is not constant stack usage. And also, your addition means the last instruction of the function is not a function call. So your code is negating any possibility of using TCO.

Upvotes: 2

Saurav Sahu
Saurav Sahu

Reputation: 13924

Your code is basically doing this:

int a = fac(n - 1);
int b = fac(n - 2); 
return a + b;

As such, the last operation before the function returns is not a function call, and thus there is no possibility of using TCO here.

Upvotes: 1

Related Questions