C++ recursive function return value

Question

As a homework, I am implementing a binary search tree, and was doing the part of searching for a position of some data (to be able to modify/remove it later), here is my piece of code:

node*& bst::search(data& x, node*& pos) {
    if (pos->get().num == x.num) {
        return pos;
    }
    if (pos->right != NULL) search(x, pos->right);
    if (pos->left != NULL) search(x, pos->left);
}

In the source file I call search(data_to_find, root). In my example I had a tree of integers of this form:

1
 2
  3

with the root pointing to 1. When I wanted to search for element 3, I was expecting to get the pointer to 3, but every single time this function returns the root itself. Then I thought maybe this had to do with the first instance of foo not returning a value, so I changed search(x, pos->right) to return search(x, pos->right) and same for left, and this time everything worked OK. This made me confused, I tried to do a few runs with the following dummy function just to understand what would it return

int foo(int x = 0) {
    if (x == 1) {
        return x;
    }
    x++;
    foo(x);
}

Although I haven't specified what to return in case the if statement is false, it stills works and outputs 1. I thought maybe foo(0) just returned whatever foo(1) returned in the recursion, to check that I tried this:

int boo() {
    return 1;
}

int foo() {
    boo();
}

and called foo(), which resulted in a "foo must return a value" error, obviously changing boo() to return boo() fixed it. Sooo my question is why is the first case outputting root? And why is the second case even working?

Flowing off the end of a function returning something different than void without a return statement is undefined behavior. You got lucky there were no nasal daemons! — Dietmar Kühl
– Dietmar Kühl, Commented Dec 29, 2016 at 20:13
It seems strange to take and return a node*&... but you don't do anything with the results of the recursive calls to search (and thus don't have a valid return). — crashmstr
– crashmstr, Commented Dec 29, 2016 at 20:21
I think you're confused about how return works in a function. Every non-void function should return something. A nested function call's return value does not automatically become the parent's return. That is, execution proceeds in a function until an explicit return is encountered within the function itself (or the function ends). — AndyG
– AndyG, Commented Dec 29, 2016 at 20:22
Also, consider enabling warnings on your compiler. For gcc, the -Wall option will say something like "no return statement in function returning non-void". — Waxrat
– Waxrat, Commented Dec 29, 2016 at 20:26

Mikel F · Accepted Answer · 2016-12-29 22:14:10Z

3

The problem you have here is that you do not propagate the return value of your recursive calls back to the original caller. As it is, when those calls return, the value is discarded.

Even worse, in cases where you don't find your match, you function as written fails to return anything, which is undefined behavior. The fact that you get the root node is more a quirk of the compiler or your current memory layout rather than a defined result.

As was pointed out by @Mike, for a binary tree, you should only be traversing one sub-tree in a search, based on whether or not your search value is greater or less than the value held by the current node. Traditionally, the left tree holds values smaller than the current node, while the right tree holds values that are greater.

edited Dec 29, 2016 at 22:14

answered Dec 29, 2016 at 20:34

Mikel F

3,6811 gold badge26 silver badges34 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mike Over a year ago

Also they should not need to search both subtrees in a bst

Collectives™ on Stack Overflow

C++ recursive function return value

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related