Is recursion possible in a static function?

Question

Is it possible to write a recursive static function in C?

Answer 1

Yes, it most certainly is. When you apply static to a function, it's not the same as a static variable within a recursive function (which is a problem if it's used in the calculations).

When applied to a function (or an object outside of a function), static simply controls whether that thing is visible outside the compilation unit (for the linker, for example).

When applied to an object within a function, static means that the variable exists beyond the duration of the function. In the context of a recursive function, it also means that there is only one copy of the variable for all recursion levels rather than one per recursion level, which is usually what's needed.

So this (what your question appears to be asking about) is perfectly okay:

static unsigned int fact (unsigned int n) {
    if (n == 1U) return 1;
    return n * fact (n-1);
}

This, on the other foot, is not okay, since the single copy of the static variable will probably be corrupted by the lower recursive layers.

static unsigned int fact (unsigned int n) {
    static unsigned int local_n;
    local_n = n;
    if (local_n == 1U) return 1;
    return fact (local_n - 1) * local_n;
}

In more detail, consider a call to fact(3):

• In the first recursive layer, local_n is set to 3, then a call is made to fact(2).
• In the second layer, local_n is set to 2, and a call is made to fact(1).
• In the third layer, local_n is set to 1, and we just return 1 because that's the base case of the recursion.

That's when things seem to start going wrong (although, technically, they started going wrong as soon as we typed in that static keyword for the local_n declarator):

• Back up into the second layer, we receive the 1 and multiply it by local_n. Now, had that variable not been static, it would have the (local) value of 2. Unfortunately, it is static, so was set to 1 in the previous step. Hence we return 1 * 1 or, ... hang on, let me check this on the calculator ..., 1 :-)
• Ditto coming back up to the first layer, we receive the 1 and multiply it by local_n which, of course, still has the value 1. So we again multiply 1 * 1 and return 1.

If you want to try it out, here's a complete program:

#include <stdio.h>

static unsigned int fact (unsigned int n) {
    static unsigned int local_n; // bad idea!
    local_n = n;
    if (local_n == 1U) return 1;
    return fact (local_n - 1) * local_n;
}

int main() {
    printf("%d\n", fact(3));
    return 0;
}

That outputs the erroneous 1 but, if you get rid of the static keyword in the local_n declarator, it will return the correct 6.