How to apply Tail Call optimization

Question

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;
}

This is an XY problem. You are actually calculating fibonacci numbers, but you are doing so using an exponential algorithm (about `O(2^n)`) — Justin, Jul 27 '17 at 03:13
`fac` is a poor name for your function. You are not computing factorials. You are evaluating Fibonacci numbers. — Happy Green Kid Naps, Jul 27 '17 at 03:34
For fun, I wrote a tail-recursive fibonacci function: https://godbolt.org/g/N8TrPc — Justin, Jul 27 '17 at 03:53
And here's an efficient tail-recursive fibonacci function: https://godbolt.org/g/U9HfY8 — Justin, Jul 27 '17 at 04:03
@Justin you program returns an error 4 which says " function call must have a constant value in a constant expression" — venaizu, Jul 27 '17 at 04:23
@venaizu That's simply because you are overflowing the value of an `int` / `long` / `long long`. `fib(100)` is too big to be contained inside native integer types — Justin, Jul 27 '17 at 04:24
@Justin one of my friend has wrote a code which can do 8181 for n. but I have no idea. how he done it. — venaizu, Jul 27 '17 at 04:39
@Justin your code doesn't run on visual studio compiler error C4430: missing type specifier - int assumed. Note: C++ does not support default-int — venaizu, Jul 27 '17 at 04:41
@venaizu Lol you haven't paid any attention to the code I wrote. Whatever you copied was obviously copied incorrectly. — Justin, Jul 27 '17 at 05:04
@Justin youre code could not use 50 for n , since you have constexpr , but one of friend he has done it to 8181 for n, do you have any idea how has done it ? — venaizu, Jul 27 '17 at 05:21
@venaizu The 8181th Fibonacci number has 1709 decimal digits (5679 binary digits), so your friend must have used some implementation of arbitrary-precision integers. Write one; it's far more fun than computing Fibonacci numbers. — molbdnilo, Jul 27 '17 at 07:54

Remy Lebeau · Accepted Answer · 2017-07-27T03:37:49.447

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.

score 1 · Answer 2 · edited Jul 27 '17 at 03:34

1

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.

edited Jul 27 '17 at 03:34

Remy Lebeau

555,201
31
458
770

answered Jul 27 '17 at 03:28

Saurav Sahu

13,038
6
64
79

How to apply Tail Call optimization

2 Answers2