When to Return a Recursive Function?

Question

I have a question on return and recursive functions.

This is again based off of a binary Tree which I am currently working on. The code is

void Tree::display()
{
    if( !root_ )
        return;

    display_r(root_);
}

void Tree::display_r(Tree *node)
{
    if( 0 == node )
        return;

    display_r(node->left_);
    std::cout << node->value_ << std::endl;
    display_r(node->right_);
}

This is working code. Compiles and runs without fail, printing the numbers from smallest to largest. However, this did not used to be so.

The code above was first written with

return display_r(node->left_);
std::cout << node->value_ << std::endl;
return display_r(node->right_);

which did not work. It simply returned without printing anything. Which makes sense, the return doesn't allow the code to move downwards.

This brought me to an interesting question. While writing the tree I was often wondering whether or not it was a good place to use return in a recursive function or not. Obviously, anytime the return is the last command executed in the block of code is okay to use. I think it's even okay to use in the display() function as

void Tree::display()
{
    if( !root_ )
        return;

    return display_r(root_);
}

So my question is: when do I know for sure I can use return, and when shouldn't I use it? Are there gray areas where it's up to me to decide what's best, and is there a safety-net? As in, "When in doubt, don't use returns in a recursive function?"

Thanks!

Answer 1

You're just using your returns, as a way to stop the execution of the function. Why not do this?

void Tree::display_r(Tree *node)
{
    if(node)
    {
        display_r(node->left_);
        std::cout << node->value_ << std::endl;
        display_r(node->right_);
    }
}

Then, if there is no node, nothing is done.

All your functions are of type void this means they should return nothing. Basically you should only use return to stop the function.

This is why none of your returns are working the way you think they should, since void functions by definition return the void, in other words, they cannot return anything.

You can return ints, or pointers, or whatever but you have to declare it, like

int function() {
    return 3;
}

Additionally, when you call a function with returns, you generally set a variable equal to what those returns are. From above:

x = function();

Tangent

You can actually use a return statement in a void function for executing void functions. This is probably generally not a great idea. Here's a simple example:

void yeah()
{
    cout << "yeah\n";
}
void test()
{
    return yeah();
}

And a simple infinite recursive loop:

void test()
{
    // !!!Caution!!! This will produce an infinite loop! 
    return test();
}

As long as what you write after the return is nothing (like a void function) this'll work, return cout<<"yeah\n" would not compile for either function, since the member function of cout that you call isn't a void function.

Answer 2

I suggest studying the return keyword more carefully and also practicing recursion a bit more.

return display_r(node->left_);
// this following code would not be executed in your example,
// you've already returned out of the function!
std::cout << node->value_ << std::endl;
return display_r(node->right_);

Here the return is necessary:

if( 0 == node )
    return;

... as this is the base case (aka general solution) for your recursive algorithm. When you encounter a null for a child, you stop, otherwise continue. Note that this code is part of an if statement. It is only executed in certain circumstances (precisely the circumstance for which you want to prematurely return out of the function and stop recursing).

In your particular case you could also write this without using return at all, and very easily:

void Tree::display_r(Tree *node)
{
    if (node) // equivalent to if (node != 0)
    {
        display_r(node->left_);
        std::cout << node->value_ << std::endl;
        display_r(node->right_);
    }
}

As an aside, and without meaning to offend, it looks as though you are borrowing from examples without quite understanding how they work. Try to think for yourself and play with the code and try to understand it. If need be, put a comment next to every instruction indicating what it does in a way that's understandable to you.

Also do try to learn the debugger; I can't emphasize this enough. A lot of university students go through their whole undergraduate degree without being taught how to use a debugger, and that's a real shame. It should be one of the first things taught! Tracing through your code with a debugger will really help you to see the behavior of the code that you write. If you aren't being taught how to use it, I recommend learning how to use it for yourself. It will show you how the machine goes through every line of code you write, step-by-step.