Recursive function in C returns value without a return

Question

So I'm writing some binary search tree functions in C (here are the node structure and insert function which work perfectly):

typedef struct searchTreeNode {
    int data;
    struct searchTreeNode *left;
    struct searchTreeNode *right;
} STNode;


void insert(STNode **proot, int data) {

    STNode *node = *proot;
    if (!node) {
        *proot = newNode(data);
        return ;
    }
    if (data <= node -> data) insert(&(node -> left), data);
    else insert(&(node -> right), data);
}

And I found that the following recursive function for finding the max value of the tree works just fine even though just the last recursive call is actually returning an integer:

int max(STNode *node) {

    if (!node) return 0;
    if (!(node -> right)) return node -> data;
    max(node -> right);
}

This means, if I am not mistaken, that it does exactly the same as this:

int max(STNode *node) {

    if (!node) return 0;
    if (!(node -> right)) return node -> data;
    return max(node -> right);
}

Where the function now returns the value it gets from the next recursion call.

Is this a known behavior where the function returns the last returned value or am I missing something?

Here is my main function with some random numbers:

int main() {

    STNode *root = NULL;
    insert(&root, 10);
    insert(&root, 13);
    insert(&root, 14);
    insert(&root, 124);
    insert(&root, 1);
    insert(&root, 8);
    insert(&root, 3);

    printf("Max value: %d
", max(root));

    return 0;
}

user_1023911 · Answer

As your first version of max does not return a value on all paths, it results in undefined behaviour when the caller tries to read that value. It is up to the compiler what to do out of that. It is not guaranteed that the compiler is inserting a return somewhere. You cannot rely on anything in that situation.

What de facto might happen on your specific platform is that the pathes

if (!node) return 0;
if (!(node -> right)) return node -> data;

write to a register where the value is returned. The recursive call max(node -> right); means that at the end one of the upper two returns will happen and the return value will be in the right register. So when max silently returns without an explicit return ...; the compiler might just issue a return machine code and leave the return register unchanged. This of course only happens because the recursive call to max is the last statement in your function (that modifies the return register).

But as said, please don't do that, it is undefined behavior and chances are high that it will cause you trouble in future.

Recursive function in C returns value without a return

1 Answers