返回递归三元矩阵 [英] Returning recursive ternary freaks out

问题描述

假设以下函数：

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

漂亮的标准递归 treeHeight 给定二叉搜索树 binaryTree 的函数。现在，我正在帮助一个朋友（他正在采取一个算法课程），我遇到了一个奇怪的问题，这个功能，我不能100％向他解释。

Pretty standard recursive treeHeight function for a given binary search tree binaryTree. Now, I was helping a friend (he's taking an algorithms course), and I ran into some weird issue with this function that I couldn't 100% explain to him.

最大值定义为 max（a，b）（（a）>（b）？（a）:( b））定义在 windef.h ），递归函数freaks out（它运行像 n ^ n times其中 n 是树的高度）。这显然使得检查具有3000个元素的树的高度需要很长时间。

With max being defined as max(a,b) ((a)>(b)?(a):(b)) (which happens to be the max definition in windef.h), the recursive function freaks out (it runs something like n^n times where n is the tree height). This obviously makes checking the height of a tree with 3000 elements take very, very long.

然而，如果max是通过模板定义的，如 std 它，一切都没关系。所以使用 std :: max 修复了他的问题。我只想知道为什么。

However, if max is defined via templating, like std does it, everything is okay. So using std::max fixed his problem. I just want to know why.

此外，为什么 countLeaves 函数工作正常，使用相同的编程递归？

Also, why does the countLeaves function work fine, using the same programmatic recursion?

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 =>

Is it because in returning the ternary function, the values a => countLeaves(n->left) and b => countLeaves(n->right) were recursively double called simply because they were the resultants?

非常感谢！

我只想链​​接一些有关该主题的文献，以供日后参考：

http://www.boostpro.com/tmpbook/preprocessor.html

http://msdn.microsoft.com/en-us/library/ z3f89ch8.aspx

I just wanted to link some literature on the subject for future reference:
http://www.boostpro.com/tmpbook/preprocessor.html
http://msdn.microsoft.com/en-us/library/z3f89ch8.aspx

两个实现之间的主要区别是：

The main difference between the two implementations being:

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

vs

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

谢谢大家！

推荐答案

宏由预处理器扩展，看代码。这意味着，例如，宏参数可能被多次评估。

Macros are expanded by the preprocessor, before the compiler gets to see the code. This means that, for example, macro parameters might be evaluated more than once.

使用你的宏，你会得到类似的东西：

With your macro, you're going to end up with something akin to:

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
    }
}

正如你所看到的以评估两个函数，然后再一个额外的时间。这是为什么宏可以是邪恶的原因。

As you can see, it's going to evaluate both functions, then one more an additional time. This is why macros can be evil.

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

You can disable the macro by defining NOMINMAX prior to including the Windows headers. Then use the function in <algorithm> instead.

如果他必须使用宏，将计算存储在变量中：

If he must use the macro, he'll have to store the calculations in a variable:

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 函数。没有重复的评估。

---

With a function, each call will be evaluated prior to calling the function. That is, it's somewhat like the previous code block. It evaluates the function's arguments, gets the results, then passes those into the std::max function. There are no repeated evaluations.

这篇关于返回递归三元矩阵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！