Is safe recursion possible in C?

Question

If the stack size in C is an implementation detail, and stack overflow is undefined behavior, is is possible whatsoever to perform any recursion at all without the possibility of summoning nose demons?

If I traverse through a data structure recursively, to give a naïve example:

struct tree {
    int leaf;
    struct tree *left;
    struct tree *right; 
}
struct tree *get(const struct tree *t, int i) {
    if (t == NULL) return NULL;
    return i == t->leaf ? t : (i > t ? get(t->right) : get(t->left));
}

Is there some sort of check that can be implemented so that this example can run safely on any standards-following C compiler, is there some sort of macro for that, or is it completely impossible, and there is no way to make this example or any similar pattern safe?

Answer 1

In the Rationale for the C99 Standard, page 24, discussing translation limits:

The Standard requires that an implementation be able to translate and execute some program that meets each of the stated limits. This criterion was felt to give a useful latitude to the implementor in meeting these limits. While a deficient implementation could probably contrive a program that meets this requirement, yet still succeed in being useless, the C89 Committee felt that such ingenuity would probably require more work than making something useful. The sense of both the C89 and C99 Committees was that implementors should not construe the translation limits as the values of hard-wired parameters, but rather as a set of criteria by which an implementation will be judged.

Provided that there exists at least one--possibly contrived and useless--program that nominally exercises the given translation limits, and that an implementation will process in a fashion consistent with the Standard, nothing the implementation does with any other program could render it non-conforming. Thus, it's not actually possible for any program to meaningfully avoid Undefined Behavior, but the authors of the Standard expected that most implementations would focus more on what would be necessary to make them useful, rather than on trying to do the bare minimum required by the Standard.