c++ - 什么时候返回递归函数？

Question

我有一个关于return 和递归函数的问题。

这又是基于我目前正在研究的二叉树。代码是

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_);
}

这是工作代码。编译和运行没有失败，从最小到最大打印数字。然而，过去并非如此。

上面的代码是先用

写的

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

这没有用。它没有打印任何东西就直接返回了。这是有道理的，返回不允许代码向下移动。

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

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

    return display_r(root_);
}

所以我的问题是:我什么时候可以确定可以使用 return，什么时候不应该使用它？是否存在由我来决定什么是最好的灰色区域，是否存在安全网？比如，“当有疑问时，不要在递归函数中使用 return 吗？”

谢谢!

Answer 1

我建议更仔细地研究 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_);

这里需要返回:

if( 0 == node )
    return;

... 因为这是递归算法的基本情况(也称为通用解决方案)。当你遇到一个 child 为 null 时，你就停止，否则继续。请注意，此代码是 if 语句的一部分。它仅在特定情况下执行(准确地说是您希望提前退出函数并停止递归的情况)。

在您的特定情况下，您也可以在不使用 return 的情况下编写此代码，而且非常容易:

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_);
    }
}

顺便说一句，并没有冒犯的意思，看起来您似乎是在借鉴示例而不完全理解它们的工作原理。尝试自己思考并使用代码并尝试理解它。如果需要，请在每条说明旁边添加注释，以您可以理解的方式说明它的作用。

还要尝试学习调试器；我怎么强调都不为过。许多大学生完成了整个本科学位，却没有学习如何使用调试器，这真是一种耻辱。它应该是最先教的东西之一!使用调试器跟踪您的代码将真正帮助您查看您编写的代码的行为。如果没有教您如何使用它，我建议您自己学习如何使用它。它将向您展示机器如何逐步处理您编写的每一行代码。