代码之家 › 专栏 › 技术社区 › David Titarenco

返回递归三元畸形

binary-tree recursion c++

David Titarenco · 技术社区 · 16 年前

假设以下函数:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        return 1 + max(findHeight(n->left), findHeight(n->right));
    }
}

相当标准的递归 treeHeight 给定二叉搜索树的函数 binaryTree . 现在,我正在帮助一个朋友(他正在上算法课程),我遇到了这个函数的一些奇怪的问题,我无法百分之百地向他解释。

Max被定义为 max(a,b) ((a)>(b)?(a):(b)) (这恰好是 windef.h ,递归函数异常(它运行类似于 n^n 时代何处 n 是树的高度)。这显然使得用3000个元素检查一棵树的高度需要非常非常长的时间。

但是,如果max是通过模板定义的,比如 std 做了,一切都好。所以使用 std::max 解决了他的问题。我只想知道为什么。

还有,为什么 countLeaves 函数运行良好,使用相同的编程递归?

int binaryTree::countLeaves(node *n) {
    if (n == NULL) {
        return 0;
    } else if (n->left == NULL && n->right == NULL) {
        return 1;
    } else {
        return countLeaves(n->left) + countLeaves(n->right);
    }
}

是因为在返回三元函数时 a => countLeaves(n->left) 和 b => countLeaves(n->right) 仅仅因为他们是结果者就被递归地双重调用?

谢谢您!

问题的答案如下

我只是想把这方面的一些文献联系起来,以备将来参考:
http://www.boostpro.com/tmpbook/preprocessor.html
http://msdn.microsoft.com/en-us/library/z3f89ch8.aspx

两种实现之间的主要区别在于:

#define max(i, j) (((i) > (j)) ? (i) : (j))

template<class T> T max (T i, T j) { return ((i > j) ? i : j) }

谢谢大家!

4 回复 | 直到 16 年前

Roger Lipscombe 16 年前

在编译器看到代码之前,预处理器会展开宏。这意味着,例如,宏参数可能会被多次求值。

用你的宏,你会得到类似于:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        return 1 + (findHeight(n->left) > findHeight(n->right)) ? // call once...
                    findHeight(n->left) : findHeight(n->right); // and ouch
    }
}

如您所见,它将评估这两个函数,然后一个额外的时间多一个。这就是为什么宏是邪恶的。

可以通过定义 NOMINMAX 在包含windows标题之前。然后使用中的函数 <algorithm> 相反。

如果必须使用宏,则必须将计算存储在变量中:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        const int leftHeight = findHeight(n->left);
        const int rightHeight = findHeight(n->right);
        return 1 + max(leftHeight, rightHeight);
    }
}

使用一个函数,将对每个调用进行求值 先前的 调用函数。也就是说,它有点像前面的代码块。它计算函数的参数,获取结果,然后将这些结果传递到 std::max 功能。没有重复的评估。

Terry Mahaffey 16 年前

那个max宏对参数求值两次-而且由于参数是递归函数调用,这可能是perf问题的根源。

ronys 16 年前

这是因为max的定义。您对findheight()进行了3次调用,而不是2次。

mukeshkumar 16 年前

更好的选择是使用以下签名声明函数:

int max(int, int)

这将防止宏的递归扩展。