返回递归三元矩阵 [英] 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屋!