何时返回递归函数？

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,什么时候不应该使用它？是否有灰色区域由我决定什么是最好的,是否有安全网？如同,"如果有疑问,不要在递归函数中使用返回值？"

谢谢!

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;

...因为这是递归算法的基本情况(也就是一般解决方案).当您遇到孩子的空值时,您会停止,否则继续.请注意,此代码是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_);
    }
}

顺便说一句,没有任何意义可以冒犯,看起来好像你是在借用例子而不太了解它们是如何工作的.尝试自己思考并使用代码并尝试理解它.如果需要,请在每条指令旁边添加注释,以便以您可以理解的方式表明它的作用.

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