递归函数中的奇怪 return 行为

Question

我有一个这样的树节点class：

class Node
{
public:
    Node();
    Node(char _value);
    ~Node();

    char getValue() const;
    Node* getParent() const;
    void addChild(Node* _child);
    bool isLeaf() const;
    bool isRoot() const;
    bool hasChild(char _value) const;
private:
    vector<Node*> children;
    char value;
    Node* parent;
};

并且我实现了一个搜索方法：

bool Node::hasChild(char _value) const
{
    if (value == _value)
        return true;

    for (auto it = children.begin(); it != children.end(); it++)
    {
        if (*it != NULL)
        {
            (*it)->hasChild(_value);
        }
    }
}

然而，当我运行这段代码时，tmp变量总是假的。如果我用调试器跟踪它，return true; 部分会执行，但递归会继续。有什么建议吗？

Node* root = new Node();
Node* a = new Node('a');
Node* c = new Node('c');

root->addChild(a);
root->addChild(c);

bool tmp = root->hasChild('a');

Answer 1

你的问题在于hasChild它调用自身的方式：

(*it)->hasChild(_value);

您调用它但不对 return 值执行任何操作。您可能想尝试 return 结果。

由于您的算法显示的是一棵未排序的树，因此这并不像在语句前加上 return 那样简单。您可能需要检查 true 和 return 但 false 意味着继续寻找：

if ((*it)->hasChild(_value))
    return true;

您还需要在函数末尾 return false。

Answer 2

您的 hasChild 代码有两个主要缺陷，它永远无法 return false，以及您调用 hasChild 的 return 值如下行从未被使用：

(*it)->hasChild(_value);

这应该可以解决您的问题（排除其余代码的任何问题）

递归函数中的奇怪 return 行为

Strange return behaviour in recursive function

c++

tree

recursion