Omitting "return" statement in a function recursively calling itself

Question

typedef struct s_node {
    int val;
    struct s_node *left_child;
    struct s_node *right_child;
} NODE;

NODE *get_node_by_val(NODE *root, int searched_val) {
    if (root != NULL) {
        if (root->val == searched_val)
            return root;
        else if (root->val > searched_val)
            get_node_by_val(root->left_child, searched_val); /**/
        else if (root->val < searched_val)
            get_node_by_val(root->right_child, searched_val); /**/
    } else
        return root;
}

Today we were talking about binary search trees. get_node_by_val above searches for a NODE in such a tree with its val matching the given searched_val. Recursively.

The point of contention is lines 12 and 14, marked with the /**/.

At first sight, or to me at least it seems, they both should have been preceded by return statements. Without the return statement, my guess is that the subtree is indeed searched, but nothing is done with the value it returns. At some point, some call to get_node_by_val will return (either NULL or a pointer to the matching node), and this value will be passed to the caller, but this may happen levels of recursion down, in which the caller would have to pass this value back to its caller, and so on, all the way up to the first caller. But without the return statement, only the caller 'immediately above' the one that returns gets that information.

Or so this would be my guess.

The problem is that this code WORKED (this happened earlier today in class, haven't tried it once again at home).

Why? How?

My uneducated guess is as follows: the deepest recursive call, the one that returns, puts its return value there on EAX. All of the calls above it don't return anything -- leaving EAX unchanged all the way up until the first caller returns (without returning anything). At the end, the caller (the one that called get_nove_by_val the very first time) sees EAX still containing the value that that deepest call put there, and figures it may as well be the value that the first call may have returned, and so everything works.

Is that what happens? Is this bad practice?

This looks like this would be undefined behavior. It just happens to work. — Carcigenicate, May 06 '19 at 20:16
maybe it works for that compiler on that particular CPU... the alternative is adding `return` so it works everywhere. it's not only bad practice, it's undefined behaviour and a good compiler should warn you about that — Jean-François Fabre, May 06 '19 at 20:20
https://stackoverflow.com/questions/10079089/implicit-int-return-value-of-c-function — Jean-François Fabre, May 06 '19 at 20:24
Nice. [modelnine's answer](https://stackoverflow.com/a/10079181/9447177) to that question expains it in the same way I proposed. — what a disgrace, May 06 '19 at 20:28
Your function is a candidate for tail call elimination, if however you're compiling does that optimization. That final recursion frame that actually returns a node might be a lot less deep on the stack then you'd guess... like, zero deep. — l.k, May 06 '19 at 21:48

score 1 · Accepted Answer · answered May 06 '19 at 20:25

You are correct, there are missing return keywords before the recursive calls to get_node_by_val. In both cases, the function exits without a return statement. Since it not a void function, this has undefined behavior.

The code behaves as expected because the register (or whatever other means appropriate for your system's ABI) used for the return value has been set in the recursive call (actually in the final recursive call) and happens do not modified by the caller until it returns to its own caller, which it does immediately. This behavior is not guaranteed and of course it is very bad practice to rely on it.

You should configure the compiler to issue useful warnings to avoid such silly mistakes: gcc -Wall -Wextra -Werror, clang -Weverything -Werror...

Omitting "return" statement in a function recursively calling itself

1 Answers1