何时返回递归函数？

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

这让我想到了一个有趣的问题。在编写树时,我常常想知道它是否是一个在递归函数中使用return的好地方。显然,任何时候返回都是代码块中执行的最后一个命令是可以使用的。我认为在display()函数中使用它甚至可以

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!

6 个解决方案

#1

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

我建议更仔细地研究return关键字,并进一步练习递归。

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).

...因为这是递归算法的基本情况(也就是一般解决方案)。当您遇到孩子的空值时,您会停止,否则继续。请注意,此代码是if语句的一部分。它仅在某些情况下执行(恰好是您希望过早退出函数并停止递归的情况)。

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.

也尝试学习调试器;我不能强调这一点。许多大学生在没有被教导如何使用调试器的情况下完成整个本科学位,这真是一种耻辱。它应该是最早教授的东西之一!使用调试器跟踪代码将真正帮助您查看您编写的代码的行为。如果您没有被教导如何使用它,我建议您自己学习如何使用它。它将向您展示机器如何逐步完成您编写的每一行代码。

#2

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.

你的所有函数都是void类型,这意味着它们不会返回任何内容。基本上你应该只使用return来停止这个功能。

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.

这就是为什么没有一个返回按照你认为应该的方式工作的原因,因为按定义的void函数返回void,换句话说,它们不能返回任何东西。

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:

此外,当您使用return调用函数时,通常会将变量设置为等于返回的变量。从上面:

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函数中使用return语句来执行void函数。这通常不是一个好主意。这是一个简单的例子:

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.

只要你在返回后写的东西没什么(就像一个void函数)这个就行了,返回cout <<“是啊\ n”不能编译任何一个函数,因为你调用的cout的成员函数不是无效功能。

#3

return display_r(node->left_);

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

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.

此代码不起作用,因为在第一次调用(递归)在左子节点上的display_r后,您从函数返回,因此从不显示打印,并且右子节点的display_r也都没有。基本上发生的事情是,在所有左节点上都会回调地调用该函数,直到没有左子节点的节点,然后所有返回的调用都返回而不打印这些值。

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.

现在,为了回答你的问题,在递归函数中使用return不仅很好,它(通常)是必不可少的算法的“停止机制”。但是,您不希望从display_r返回值,因为它不返回任何内容(void)。此外,使用“return XXX”令人困惑和错误。关于void函数。这意味着他们会返回某种类型的价值。因为在我们的例子中,display_r只返回一个void,所以这不会产生编译错误,但一般来说,使用“return”是正确的形式。 (当没有任何函数或值后调用)返回空格时。在你的情况下,递归函数的停止机制是当你“显示”一个空节点时,所以第一次返回是唯一的一个nessesary。

#4

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

return退出当前函数,因此有两个不受程序控制块影响的返回语句,如下所示:

return x; return y;

返回x;回归;

Will always only cause x to be returned.

永远只会导致x返回。

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

C / C ++本身并不真正支持协同例程/ yield返回(这可能是你在有两个return语句时所期望的)

#5

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.)

当你的所有函数都返回'void'时,在这种情况下,它们返回的内容并不重要。如果将“return”语句放在自己的行上,您可能会更容易查看代码。 (您的代码几乎给人的印象是'return'被用作'goto'或'call'语句。)

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. :)

您可能会发现使用树结构学习“广度优先搜索”和“深度优先搜索”以及“预订”,“按顺序”和“后订购”树遍历会很有帮助。一开始可能听起来令人生畏,但迟早它会全部点击,递归功能对你来说会容易得多。 :)

#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.

你也可以考虑在语言和/或环境中练习递归,当你犯这样的错误时会给你警告。例如,Eclipse和Java将在第一个返回语句之下的任何内容上给出一个简洁的“无法访问代码”错误。

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]

[code] int counter(int count){if(count == 0)return; // STOP condition else计数器(count--); // Action(count -1)和递归调用(counter())。 } [/ code]

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

我确信这三个步骤的官方名称更多。