3

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.

1
  • 5
    Just pass it as a param (possibly by pointer if the context data is larger than a pointer). If you have multiple context variables, bundle them as a struct. C++ closures are typically implemented exactly like that: an anonymous class, and performing a call involves an implicit this pointer argument. Don't bother with the register keyword, it is only advisory, is mostly ignored during optimization, and in any case only affects local variables and not a function call.
    – amon
    Nov 13, 2023 at 22:29

2 Answers 2

6

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.

8

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.

3
  • 1
    And in the case of C specifically here, your can approximate that as a struct, with functions that take a struct instance as a param (akin to this).
    – Alexander
    Nov 14, 2023 at 0:38
  • 3
    @Alexander yes. My C++ professor (who was on the language committee) used to love telling us that the only difference between objects and structs was whether or not members defaulted to public. Nov 14, 2023 at 0:43
  • 1
    @candied_orange And that is of course 100% true. Except using “public” or “private” also means that the C “plain old data structure” rules don’t apply anymore.
    – gnasher729
    Nov 14, 2023 at 11:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.