草庐IT

c++ - 返回递归三元怪胎

coder 2024-02-08 原文

假定以下函数:

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

用于给定二叉搜索树 binaryTree 的非常标准的递归 treeHeight 函数。现在，我正在帮助一个 friend (他正在上一门算法类(class))，我遇到了这个函数的一些奇怪问题，我无法 100% 向他解释。

max 被定义为 max(a,b) ((a)>(b)?(a):(b)) (恰好是 中的 max 定义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) }

谢谢大家!

最佳答案

宏在编译器看到代码之前由预处理器展开。这意味着，例如，可能会多次评估宏参数。

使用您的宏，您最终会得到类似于:

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 header 之前。然后使用<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功能。没有重复评价。

关于c++ - 返回递归三元怪胎，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2445514/

怪胎ampcodefindHeightreturnc++recursionbinary-tree

有关c++ - 返回递归三元怪胎的更多相关文章

  1. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby - 检查字符串是否包含散列中的任何键并返回它包含的键的值 - 2

    我有一个包含多个键的散列和一个字符串，该字符串不包含散列中的任何键或包含一个键。h={"k1"=>"v1","k2"=>"v2","k3"=>"v3"}s="thisisanexamplestringthatmightoccurwithakeysomewhereinthestringk1(withspecialcharacterslike(^&*$#@!^&&*))"检查s是否包含h中的任何键的最佳方法是什么，如果包含，则返回它包含的键的值？例如，对于上面的h和s的例子，输出应该是v1。编辑:只有字符串是用户定义的。哈希将始终相同。 最佳答案

  4. ruby - Ruby 中的隐式返回值是怎么回事？ - 2

    所以我开始关注ruby​​，很多东西看起来不错，但我对隐式return语句很反感。我理解默认情况下让所有内容返回self或nil但不是语句的最后一个值。对我来说，它看起来非常脆弱(尤其是)如果你正在使用一个不打算返回某些东西的方法(尤其是一个改变状态/破坏性方法的函数!)，其他人可能最终依赖于一个返回对方法的目的并不重要，并且有很大的改变机会。隐式返回有什么意义？有没有办法让事情变得更简单？总是有返回以防止隐含返回被认为是好的做法吗？我是不是太担心这个了？附言当人们想要从方法中返回特定的东西时，他们是否经常使用隐式返回，这不是让你组中的其他人更容易破坏彼此的代码吗？当然，记录一切并给出

  5. ruby-on-rails - ruby 日期方程不返回预期的真值 - 2

    为什么以下不同？Time.now.end_of_day==Time.now.end_of_day-0.days#falseTime.now.end_of_day.to_s==Time.now.end_of_day-0.days.to_s#true 最佳答案 因为纳秒数不同:ruby-1.9.2-p180:014>(Time.now.end_of_day-0.days).nsec=>999999000ruby-1.9.2-p180:015>Time.now.end_of_day.nsec=>999999998

  6. ruby - 从 String#split 返回的零长度字符串 - 2

    在Ruby1.9.3(可能还有更早的版本，不确定)中，我试图弄清楚为什么Ruby的String#split方法会给我某些结果。我得到的结果似乎与我的预期相反。这是一个例子:"abcabc".split("b")#=>["a","ca","c"]"abcabc".split("a")#=>["","bc","bc"]"abcabc".split("c")#=>["ab","ab"]在这里，第一个示例返回的正是我所期望的。但在第二个示例中，我很困惑为什么#split返回零长度字符串作为返回数组的第一个值。这是什么原因呢？这是我所期望的:"abcabc".split("a")#=>["bc"

  7. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  8. ruby - 为什么 Integer.respond_to?( :even? ) 返回 false？ - 2

    我一直在研究RubyKoans，我发现about_open_classes.rbkoan很有趣。特别是他们修改Integer#even?方法的最后一个测试。我想尝试一下这个概念，所以我打开了Irb并尝试运行Integer.respond_to?(:even?)，但令我惊讶的是我得到了错误。然后我尝试了Fixnum.respond_to?(:even?)并得到了错误。我还尝试了Integer.respond_to?(:respond_to?)并得到了true，当我执行2.even?时，我也得到了true。我不知道发生了什么。谁能告诉我缺少什么？ 最佳答案

  9. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  10. ruby - Time.to_i 是否总是以 UTC 返回自 EPOCH 以来的秒数？ - 2

    无论时间在哪个时区表示，时区差异是否总是被忽略？直觉上，对于那些使用UTC+2的人来说，从EPOCH开始经过的秒数应该更高。然而，事实并非如此。 最佳答案 Epoch基于utc时区https://en.wikipedia.org/wiki/Unix_time它与您当前所在的时区无关。 关于ruby-Time.to_i是否总是以UTC返回自EPOCH以来的秒数？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.

随机推荐