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

return exits the current function, so having two return statements unaffected by program control blocks like this:

return x; return y;

Will always only cause x to be returned.

C/C++ doesn't really support co-routines/yield returns natively (which is probably what you were expecting when you had two return statements)

Answer 3

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.

Answer 4

I always find it helpful to think of mathematical induction when writing recursive functions: You need a base-case and an inductive-case for induction to work. Recursion is not too different: you need a method/routine/function that works on reducing the problem to the base case, and you need a method/routine/function that can handle the base case.

In other words, you need something that can terminate the recursive function, and you need something that works the current input towards the terminating state.

Once you have that in mind, it is easier to think of where to put the return statements:

When all your functions return 'void', in this case, what they return doesn't much matter. You might have an easier time viewing your code if you place the 'return' statements on their own lines. (Your code almost gives the impression that 'return' is being used as a 'goto' or 'call' statement.)

When your functions return data (rather than perform side-effects, such as printing) then it will probably be more clear to you where the return statements must go: they must go after you have computed the data you need for the case you're working with, whether it is a base-case or an inductive-case.

You might find it helpful to study "Breadth-first search" and "Depth-first search" with tree structures, as well as "pre-order", "in-order", and "post-order" tree traversal. It might sound daunting at first, but sooner or later it will all click, and recursive functions will be far easier on you. :)

Answer 5

return display_r(node->left_);

std::cout << node->value_ << std::endl;

return display_r(node->right_);

This code did not work because after calling (recursively) for the first time to display_r on the left child node, you return from the function and thus the print is never displayed, and neither are the display_r for the right child nods. Basically what happens is that the function is called recuresively on all left nodes until a node with no left child node, and then the recuresive calls all return without ever printing the values.

Now, to answer your question, it is not only fine to use return in recursive functions, it is (usually) nesecessary as a "stop mechanism" for the algorithm. Here however you do not want to return the value from display_r since it returns nothing (void). Furthermore it is confusing and errorsome to use "return XXX;" on void functions. It implies that they return some type of value where they don't. Since in our case display_r only returns a void then this did not generate a compile error, but generally, it is the correct form to use "return;" (without any call to a function or value afterwards) when you return a void. In your case, the stopping mechanism for the recursive function is when you are "displaying" a null node, so the first return is the only one nessesary.

Answer 6

You could also consider practicing recursion in a language and/or environment that gives you warnings when you make mistakes like this. Eclipse and Java will, for example, give you a neat "Unreachable code" error on anything below that first return statement.

As for recursive functions, you just have to remember to give it three parts:

• The 'stop' condition - when should it actually return something and stop going down the 'tree'
• The 'Action' - have the function do something.
• The 'recursive call' - re-call the same method you're writing at that time.

Of course, the action can in some cases be omitted, and the second and third steps can be interchanged. A simple counter would be created as such in pseudocode:

[code] int counter(int count) { if (count == 0) return; // STOP condition else counter(count--); // Action (count -1) and recursive call (counter()). } [/code]

I'm sure there's more official names for those three steps though.