Why we can't use static variables to achieve tail recursion?

Question

I am learning C, so I am writting some little exercises in C to practice the language.

I have experience with functional code, so I love recursion. I think that it would be great to achieve tail recursion using C static variables, so additional arguments or helper functions would not be required.

This code to calculate a factorial using recursion, fails:

long long int fact(int n)
{
    static long long int result = -1;

    if(n <= 0) {
        if(result < 0)
            return 1;
        else {
            long long int temp = result;
            result = -1;
            return temp;
        }
    } else {
        result *= n;
        fact(n - 1);
    }
}

However, for some reason, I cannot do this in C. Is there an idiom to the same that? Is it just my compiler? What about memoization?

Thanks a lot.

Answer 1

Your code is broken since it has a control path where it doesn't return a value. This works fine:

long long int fact(int n)
{
    static long long int result = 1;

    if(n <= 1) {
        long long int temp = result;
        result = 1;
        return temp;
    } else {
        result *= n;
        return fact(n - 1);
    }
}

GCC does successfully transform the tail recursion to iteration.

In general, I think the reason to avoid using statics for tail recursion is simply because the function loses reentrancy. So much code ends up having to run in a multithreaded environment these days that it's hard to justify leaving function-local static "landmines" in code. I do admit this is as much opinion as technical argument. The non-static tail recursive code:

static inline long long int fact_(int n, long long int result)
{
    if(n <= 1) {
        return result;
    } else {
        return fact_(n - 1, result * n);
    }
}

long long int fact(int n)
{
    return fact_(n, 1);
}

is if anything a bit easier to write - notably both versions are exactly 13 LOC - and compiles just as efficiently to iteration but without needing static data.