A question about the differing behaviours of local static variables in C

user_19012333 0
Viewed 55

I've been exploring the behaviour of static variables in C, using the following piece of code:

#include <stdio.h>

int f(int n)
{
    static int r = 10;

    if (n <= 0)
        return 7;

    if (n > 2)
        return f(n-1) + r;       // Important line
    else{
        r = 17;
        return f(n-1) + n;
    }
}

int main(void)
{
    int n = 4;
    printf("%d\n", f(n));

    return 0;
}

Now if you note the "Important line" in the code (return f(n-1) + r), it calls the function f first, which changes the static variable, r.

However, if I changed that line to return r + f(n-1), I expect that r will get stored in a temporary register, and only then will the function f be evaluated. However this does not seem to happen, as in both the cases, the function f is evaluated first. I've even checked the assembly code generated by the compiler and it calls the function first in both cases.

But, if I change the line to return (r+2) + f(n-1), then (r+2) is evaluated first and stored in a temporary register and only then is the function f evaluated.

And if I again change the line to return f(n-1) + (r+2) then it's the function f that gets evaluated first.

Thus, using return r + f(n-1) and return f(n-1) + r in the program give the exact same output.

However, using return (r+2) + f(n-1) and return f(n-1) + (r+2) gives different outputs.

I can't understand why this discrepancy in the behaviour of static variables. According to my understanding, in return r + f(n-1) clearly r should be evaluated first, but this is not happening. Can anyone please explain why ? And why is this behaviour not consistent ? Why does it change if I use (r+2) instead of r ?

static-variables recursion static c variables
2 Answers

C leaves those decisions up to the compiler.

Your expectations are unfounded.

You talk about registers, but C doesn't require a machine that uses registers.

You talk about the relative order in which the operands of + are evaluated, but C has no requirements about this. The compiler is free to evaluate them in the order of its choice.

The discrepancy is rooted in the false assumptions you made. All your questions are answered by: It's up to the compiler.

user_5899240

However, if I changed that line to return r + f(n-1), I expect that r will get stored in a temporary register, and only then will the function f be evaluated.

No.

First of all, whether a variable is temporarily stored in a register or not is an implementation detail that only affects optimization, not the result of the program. Also in the recursion case, it cannot reasonably store a variable in a register if that register isn't stacked as per calling convention, or it would run out of registers pretty quick. And how would it know which register to use, since the machine code is the same no matter how deep in the recursion we are.

Regarding program behavior, then what applies in this case is the order of evaluation of the operands, which in case of + is unspecified/unsequenced (C17 6.5/3). Meaning that you cannot know if r or f(n-1) will get evaluated first, nor does the compiler need to order the evaluation consistently from case to case. And different compilers may order them differently, of course.

You should not use r in the same expression as in the function call. If r should always stay the same within a certain scope of a recursive call, then you need to manually store it in a temporary variable upon entering the function.

Notably a plain loop would have been much faster and less error prone than recursion. It would also eliminate the need for the static variable, so it would be thread-safe, unlike your present code. There are very few cases when recursion should actually be used in C and this isn't one of them.

user_5845180
Related