2

I'm a computer science college student. Yesterday, I have a class about Binary Search Tree using C++. We are taught by lab assistants in that class.

They define the node in the tree as a struct like this :

struct Data{
    char name[15];
    int age;
    Data *left,*right;
};

and they give us a code to search within the BST like this:

// temp is current node, name is the value of the node to be searched for.
Data* search(Data *temp,char name[]) {
    if(strcmp(temp->name,name)>0)
        search(temp->left,name);
    else if(strcmp(temp->name,name)<0)
        search(temp->right,name);
    else
        return temp;
}

I notice that code is wrong. If the function gets into the first or the second if block, it will not execute any return statement.

But when the lab assistant run the code, it works just fine.

I thought maybe this behaviour is compiler specific. But when I tried that code on gcc, the function also work fine. (our university uses microsoft visual c++ compiler)

Can anyone explain what is happening? why is this code working?

PS: ignore other errors such as when the node is empty, the value is not found, etc.

Teddy
  • 95
  • 1
  • 7
  • 3
    duplicate of: http://stackoverflow.com/questions/1610030/why-can-you-return-from-a-non-void-function-without-returning-a-value-without-pr –  May 11 '12 at 09:27
  • The code is ok, it's a recursive function. – ott-- May 11 '12 at 09:27
  • @alegen: I think he's not asking why it's not a compiler warning/error, he's asking why it works at runtime. So different from the Q you linked to. – tinman May 11 '12 at 09:28
  • 1
    @ott: the code is not ok, because after the return from recursion we don't return anything. – Vlad May 11 '12 at 09:31
  • @Vlad Ok, yes. It silently returns the return value from the recursive call. So the last `else` should be removed and the `return` shifted left a bit. – ott-- May 11 '12 at 09:44
  • @Ott no that won't do it. If you do that the function will always return the position of the first function call. – Teddy May 11 '12 at 09:57
  • @Teddy Seems I'm still asleep tho I got up 5 hours ago. So twice `if (strcmp ... return search (...` and then the simple `return temp`. – ott-- May 11 '12 at 10:14

2 Answers2

8

It's just undefined behavior.

It appears to work because there's one register that holds the return value. In the deepest paths of the recursion tree, the temp is moved into that register, and never cleared or changed afterwards, so that register will contain the correct node until the first call returns.

When the first call returns, the calling context checks that register for the return value, which happens to be correct. But you shouldn't rely on this. It's not safe to assume it will always work.

Luchian Grigore
  • 253,575
  • 64
  • 457
  • 625
  • Thanks for the answer. Is there any way to prove this code has undefined behavior? You know, The lab assistant won't believe what I say. – Teddy May 11 '12 at 09:52
  • @Teddy the only way to prove it's undefined is looking it up in the standard. – Luchian Grigore May 11 '12 at 09:55
  • @Teddy http://stackoverflow.com/questions/367633/what-are-all-the-common-undefined-behaviour-that-a-c-programmer-should-know-ab see the first answer, bullet point 12 – Luchian Grigore May 11 '12 at 09:57
1

Typically, you've got one hardware register used to return value from a function (that'd be %EAX on i686, for instance). If the last thing you did in your function is calling another function and the intended return value is the result of that function, it may occur that %EAX value hasn't been trashed and is nicely retrieved by the caller.

That's subject to many hypothesis, however, and you shouldn't expect it to be reliable in any way. First of all, the compiler can detect that you're not using the return value of search(), so it might decide to optimize away that call if it has hints about search() having no side effects. If it's capable of inlining the search call, it could partly optimize it away.

There may be other architectures (iirc, that'd be the case with IA64) where the calling convention are more subtle, and where the registers used for returning values in one function are not the same as in the caller function. So your code relies on platform-dependent details to be working while it's supposed to be a high-level (and portable) language.

PypeBros
  • 2,607
  • 24
  • 37