Maintaining global states in a recursive function

Question

I am writing a recursive function. Some of the parameter data is different for each recursive call but some of the data only need to have one copy existing at any one time during the recursive call. For example a variable to keep track of the recursion depth when iterating/recursing on a recursive data structure (octree):

void recurse(const uint16_t *ptr) {
    const uint16_t node = *ptr;
    if (node & FLAG_MASK) {
        ptr = (node_to_set(ptr) + (node & DATA_MASK))->x; /* These are just bitwise manipulators
            and their exact behavior is not important, in short, ptr changes */
        for (uint_fast8_t i = 0; i < 8; recurse(ptr + i++));
        return;
    }
    printf("%d\n", node);
}
void iter_recursive(const Octree *const octree) {
    recurse(&octree->base);
}

This seems to lack the inefficiencies of recursion since the alternative (iterative) approach entails creating a 'stack' of pointers anyway. Each recursion will need its own copy of ptr anyway so the overhead of allocating new stack memory each call is not 'wasted' or 'unnecessary' in any sense.

However, in this structure, what if I have data that I do, in fact, only want a single copy of? Such as the current recursion depth or data that does not change after the initial first call.

I could add a uint_fast8_t depth parameter to the recursive function, and call it with 0 the first time, and call it with depth+1 recursively. However this of course creates a new copy of depth each recursion but in theory only a single one is necessary. This does introduce unnecessary overhead and clutter for each new state that is not specific to each recursive call.

Another solution is to create a global variable. However, I prefer to avoid global states when possible. For example, doing so would make the code not thread safe.

In C++ I could probably make the function capture the local variables of a wrapper function like so:

void iter_recursive(const Octree *const octree) {
    int depth = 0;
    auto recurse = [depth](const uint16_t *ptr){
        const uint16_t node = *ptr;
        if (node & FLAG_MASK) {
            ++depth;
            ptr = (node_to_set(ptr) + (node & DATA_MASK))->x;
            for (uint_fast8_t i = 0; i < 8; recurse(ptr + i++));
            --depth;
            return;
        }
        printf("%d\n", node);
    }
    recurse(&octree->base);
}

However this is a speculative C++ only solution that I have not tested so this could be totally wrong, and cannot be used in pure C. And C++ is higher level than C so I do not know what kind of overhead is actually involved in capturing local variables.

What is the most memory-efficient way to pass data to recursive functions that do not need to be copied on each recursion? For example, if the a parameter is unchanging and declared as const register so no address exists and cannot be changed, is there guarantee that the parameter will actually be copied, given that there is no observable behavior that would differentiate whether they were copied or not? (I do not know enough about how computer hardware works to know if this optimization would actually be possible) In this case, would it be most efficient to pass a pointer to a structure containing all the items that should not be copied? Even if the total size of the items is less than the size of a pointer?

I found this but that is a JavaScript question and therefore not applicable to my use-case.

Answer 1

Using global data is bad because your recursive function cannot be used from multiple threads. Which is a horrible trap, because 99.99% of the time it’s not called from multiple threads at the same time, and in the 0,01% case you have a bug that you cannot reproduce.

Just put all the information you want to stay unchanged into a struct in a local variable and pass the address or a reference to the first call, or pass the struct itself by value, which is easier but may be slower, or if the data is just one or two primitives then pass them directly.

Answer 2

Global and in scope are different things. Either a closure or an object will give you a place to declare fields that are accessible from call to call, maintain state, and are not global.

In closures this is called the enclosing lexical scope. In objects its called member fields.