What is "Clang-Tidy: Function is within a recursive call chain" ? How to fix it?

Question

I'm writing a function dealing with string in C, which is recursive. Basically what it does is to find a string between some characters and '\0'. If before it finds '\0', it hits on the particular characters, it will recursively call itself.

When writing it in CLion, I see a warning from Clang-Tidy, which I never saw before. It says

Clang-Tidy: Function 'function' is within a recursive call chain

I'm wondering is it a new feature of CLion 20.02 (I recently updated it)? Moreover, how can I fix it?

Here's my code.

char *function(char *pos, <some arguments>) {
    char *temp = pos + 1;
    while (1) {
        if (*temp == '\0') {
            return temp;
        } else if (*temp == '<something>') {
            *temp = '\0';
            if (*(temp + 1) == '\0') {
                return function(temp + 1, <some arguments>);
            } else if (*(temp + 1) == '<something>') {
                if (*(temp + 2) == '\0') {
                    return function(temp + 2, <some arguments>);
                } else {
                    return function(temp + 1, <some arguments>);
                }
            } else {
                return function(temp, <some arguments>);
            }
        }
        temp++;
    }
}

Waterhouse

Isn't that simply a warning which basically tells you: "Hey, you're using recursion, which might be a problem, because a recursion can potentially lead to a stack overflow". – Archaize

@Archaize It seems that you are right. But I just want to make sure that. because I never saw it before. – Waterhouse

Answer 1

Yes, recent Clang-Tidy diagnoses recursion. If you are intentionally writing a recursive function, and you are confident that it cannot be used in a context where recursion is disallowed (see references in the Clang-Tidy docs, for example), then it is reasonable to ignore that warning. Since "disallowed" is much more often a policy question than a technical one, you should consider clearly documenting that the function is recursive. And you should consider not using recursion, which is generally better for real-world code.

This check was not in Clang-Tidy 10. I'm having trouble finding docs for Clang-Tidy 11, but the release notes for Clang-Tidy 12 do not list it as new, so it looks like it was added in 11.

Propylite

to add to this question: while learning recursion is a good thing, in real world recursion should be avoided in C and C++ as it can easily lead to stack overflow. So to fix this: if you need the recursion (e.g. for learning purposes) silence this warning or convert the function to be non-recursive (with classic loops). – Wilbanks

So theoretically it doesn't mean there's something wrong in my recursion, but is just a kind reminder? @John – Waterhouse

Yes, @citrate. The docs for the check indicate that it unconditionally flags recursive call chains, on the basis that there are contexts where you should not use recursion. It is not sufficiently context-sensitive to recognize whether the call chain is used in such a context; in fact, in most cases, it is impossible for Clang-Tidy to know that. – Propylite

Recursion is not just for "learning". In the particular example, recursion is probably not recommended. But in the real world there are plenty of reasons for using recursion, like performing an action for all nodes in a tree or iterating over files in a filesystem. – Justify

@Justify the things you mentioned are exactly the things you should not be using recursion for in the real world, unless you can somehow guarantee the maximum depth of your tree or filesystem, since it can easily lead to stack overflow – Chip

@Chip how else would you solve it? – Wherever

How else would I solve what exactly? Any recursive algorithm (i.e. implemented with recursive function calls) can be turned into a non-recursive one (i.e. implemented using simple loops) by using a manually-managed stack, list or queue data structure to keep track of your state. 99 out of 100 times the iterative variant will perform better and will not require potentially unbounded amounts of memory on the call stack, which is generally a very finite block of memory (on the order of a few MB). – Chip

... and tail-recursive algorithms don't require even that manually-managed stack / list / queue. – Propylite

... but tail-recursive functions are nearly always optimized (at least by gcc and clang) to use one stack frame only. – Mungovan

Just to add a bit to the discussion: BFS is is the most typical example of this non-recursive algorithm with a manually managed stack. BFS is better than DFS in real-world code almost all the time and usually faster too. – Matronly

In functional programming, recursion is the standard. Loops are inherently unusable because they require mutability. – Album

@Chip All you've really done there is manually written a stack instead of using the one provided for you by the compiler. You still have all the same issues. That said I feel using the call stack makes it very easy to include unnecessary state and forget about memory limitations. Clang-tidy arguably removes this concern by highlighting it. – Epsilon