What's the meaning of the "return" here?

Question

meiyantao 0 Light Poster

19 Years Ago

This codeblock comes from Mr Weiss's book "Data Sturucture and Algorithm Analysis in C++"(Third Edition). I have some questions about it.

/**
*This is a member function from the BinarySearchTree class.
*And It try to find whether there's a element equal to x in
*the binary search tree.
*/
bool BinarySearchTree::contains(const int & x, BinaryNode *t){
if(t==NULL)
return false;
/**
*Weiss put the following two sentences to the end of this 
*codeblock with an "else".But I think put it here can make 
*the code more readable.Is it an error?
*/
if(x == t->element)
return true; 
/**
*When I implemented these, I haven't added 
*"return" before recursive functions.
*Why must add "return" in the following sentences?
*How many times will the "return" really
*return when the promgram run?
*What will be happened,if I delete these "return"?
*/
if(x < t->element)
return contains(x,t->left); 
else if(t->element < x )
return contains(x,t->right);
}

My questions have put in the codeblock.I know that my English is bad,if you find some errors in my English syntax,please help me too! As you know,it's impossible to study C++ well without English.
Thanks ^_^

c++

6 Contributors
8 Replies
189 Views
4 Days Discussion Span
Latest Post 19 Years Ago Latest Post by WolfPack

Dani AI

Generated 6 Months Ago

Short answer: the return hands the boolean result produced by the recursive call back to the caller and ends the current function invocation. In a line like return contains(x, t->left); the current frame calls contains, waits for that call to finish, then immediately returns whatever boolean value it got. That returned value is propagated up the chain until the original caller receives it.

Each recursive call has its own stack frame. If the search visits k nodes along the path, there will be k calls and k returns executed (one return per frame as the stack unwinds). The base case (found or NULL) produces the boolean value; every caller on the path simply returns that same value to its caller. This is why return is needed: without it the value from the deeper call is discarded.

If you remove the return and just call the recursive function, the containing function will reach the end without returning a value — for a non-void function this is undefined behavior. Modern compilers will usually warn (e.g. "control reaches end of non-void function") and the program can behave unpredictably, so always return a value from every path.

If recursion depth is a concern, an iterative traversal avoids deep stacks and is simple to write. For example:

bool containsIter(const int &x, BinaryNode *t) {
    while (t != NULL) {
        if (x == t->element) return true;
        t = (x < t->element) ? t->left : t->right;
    }
    return false;
}

’s cleaned-up explanation is correct about the propagation; this note adds the important practical points: why omission is undefined, how many returns run, and an iterative alternative if you need to avoid deep recursion.

All 8 Replies

WaltP 2,905 Posting Sage w/ dash of thyme

19 Years Ago

This codeblock comes from Mr Weiss's book "Data Sturucture and Algorithm Analysis in C++"(Third Edition). I have some questions about it.

First of all, please format your code so it can be followed. I'll format it as I go...

/**
*  This is a member function from the BinarySearchTree class.
*  And It try to find whether there's a element equal to x in
*  the binary search tree.
*/
bool BinarySearchTree::contains(const int & x, BinaryNode *t)
{
    if (t == NULL)
    {
        return false;

    }
/**
* Weiss put the following two sentences to the end of this 
* codeblock with an "else".But I think put it here can make 
* the code more readable.Is it an error?
*/
    if (x == t->element)
    {
        return true; 
    }
//// The way the function is written, it doesn't seem to matter 
//// where this IF goes since each recursive call is part of a 
//// RETURN statement.

/**
*When I implemented these, I haven't added 
*"return" before recursive functions.
*Why must add "return" in the following sentences?
//// Because when the function finally gets to the end of 
//// the search, the value is passed back via the RETURN 
//// statements.  So the function returns the value, and 
//// upon returning returns the value again.  It just keeps 
//// passing  the value back to the previous recursion

*How many times will the "return" really
*return when the promgram run?
//// Exactly the same number of time the function is called...

*What will be happened,if I delete these "return"?
//// The function won't work.  Each return below actually 
//// calls the function again with the next node value to 
//// be tested.
*/
    if (x < t->element)
    {
        return contains(x,t->left); 
    }
    else 
    if (t->element < x )
    {
        return contains(x,t->right);
    }
}

So here's a simplified version of the function.

bool BinarySearchTree::contains(const int & x, BinaryNode *t)
{
    if (t == NULL)
    {
        return false;
    }

    // if this element is before the one we're looking for, 
    //   call the function again with the next value (left)
    if (x < t->element)
    {
        return contains(x,t->left); 
    }
    // This element is not before the one we're looking for...
    
    // if this element is after the one we're looking for, 
    //   call the function again with the previous value (right)
    if (t->element < x )
    {
        return contains(x,t->right);
    }
    // This element is not before nor after.  Therefore it IS
    //    the one we're looking for.  We found it so return TRUE
    return true; 
}

Narue 5,707 Bad Cop

19 Years Ago

I'm most certainly not a fan of Weiss' code, but the book you have is half decent in terms of coverage. His stuff is noticeably dumbed down, but if you want to take your trees to the next level, try .

~s.o.s~ commented: Good thing you updated your site. Too bad there is no button for commenting.. ;-) +20

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Good thing you updated your site. Too bad there is no button for commenting.. ;-)

meiyantao 0 Light Poster · Answer 1 · 2007-06-05T11:59:40+00:00

meiyantao 0 Light Poster

19 Years Ago

Thank you very much!

Ancient Dragon 5,243 Achieved Level 70 Team Colleague Featured Poster · Answer 2 · 2007-06-05T17:26:00+00:00

As you know,it's impossible to study C++ well without English.
Thanks ^_^

Probably because English has become the universal language of business. Anyone who needs to conduct business in todays global world needs to know English.

And the English you posted looks great to me. :)

meiyantao 0 Light Poster · Answer 3 · 2007-06-05T22:20:44+00:00

So here's a simplified version of the function.

bool BinarySearchTree::contains(const int & x, BinaryNode *t)
{
    if (t == NULL)
    {
        return false;
    }
 
    // if this element is before the one we're looking for, 
    //   call the function again with the next value (left)
    if (x < t->element)
    {
        return contains(x,t->left); 
    }
    // This element is not before the one we're looking for...
 
    // if this element is after the one we're looking for, 
    //   call the function again with the previous value (right)
    if (t->element < x )
    {
        return contains(x,t->right);
    }
    // This element is not before nor after.  Therefore it IS
    //    the one we're looking for.  We found it so return TRUE
    return true; 
}

Yes,thank you.It's beautiful.Your code is most the same as Mr Weiss's. Ha,I am trying to implement all of his book,but I can't write them without looking his code.

meiyantao 0 Light Poster · Answer 4 · 2007-06-07T00:52:44+00:00

I'm most certainly not a fan of Weiss' code, but the book you have is half decent in terms of coverage. His stuff is noticeably dumbed down, but if you want to take your trees to the next level, try .

I will try to do it,thank you very much!

ss339 0 Newbie Poster · Answer 5 · 2007-06-08T07:44:56+00:00

Probably because English has become the universal language of business. Anyone who needs to conduct business in todays global world needs to know English.

Thats the problem man....

Many people that dont have english as first language, it is much harder...

I know this first hand..

WolfPack 491 Posting Virtuoso Team Colleague · Answer 6 · 2007-06-09T07:56:20+00:00

! As you know,it's impossible to study C++ well without English.

If you have good C++ books written in or translated to a language you understand, English is not a necessity. Ask any Japanese C++ programmer. You will find it hard communicating in an English IT forum like this, but you can learn C++ without English.

What's the meaning of the "return" here?

Dani AI

Recommended Answers Collapse Answers

All 8 Replies

Recommended Answers