C++ 中的递归函数

Question

如果我有这个递归函数：

int mystery(int n) {

if ( n == 0 || n == 1 ||  n ==  2) return  n ;
 return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

我正在寻找神秘（20）。

如何查明计算函数时执行了多少次加法运算以及计算 mymy(20) 时调用了多少次 Mystery() ？

我尝试添加一些 cout 语句，例如：

int mystery(int n) {
    if ( n == 0 || n == 1 ||  n ==  2) {
      cout << n << endl; 
      return  n ;
    }
        cout << n << endl;
    return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

但我无法真正理解它，因为输出了一千多个数字。而且我不相信这些 cout 语句能告诉我执行了多少次加法运算以及有多少次调用 Mystery() 来计算 Mystery(20)？

感谢您的任何帮助！

Answer 1

最简单的方法是增加全局（或静态全局）变量。

类似于获取神秘呼叫的数量：

int nb_of_invok = 0;
int mystery(int n)
{
  nb_of_invok++;
  ...your code here...
}

这可以获取添加的数量：

int nb_of_invok = 0;
int nb_of_add = 0;
int mystery(int n)
{
  nb_of_invok++;
  if(...)return n;
  nb_of_add++;
  return(...);
}

Answer 2

如果我理解正确的话...您可以使用静态计数器变量并在每次调用该方法时递增该变量。或者，您可以传递对计数器的引用并仅递增该引用。

Answer 3

这可以用数学来算出来。但如果您想凭经验测量它，您可以在函数中使用静态计数器。这个逻辑也很容易扩展到计算加法的数量。

int mystery(int n) {
    static int invocations = 1;

    cout << "mystery has been invoked " << invocations++ << " times.\n";
    if ( n == 0 || n == 1 ||  n ==  2) {
      return  n ;
    }
    return (mystery(n-1) + mystery(n-2) + mystery(n-3))  ;
}

您还可以使用全局变量。但我不喜欢这两种解决方案。它们使多线程变得困难，并且违反了一些重要的设计原则。作为一次性回答这个问题，然后从代码中删除它们很好，但是如果我希望将其作为永久功能，我会做的是：

#include <iostream>

class counted_mystery {
   public:
    counted_mystery() : invocations_(0), additions_(0) { }

    unsigned int getInvocations() const { return invocations_; }
    void resetInvocations(unsigned int newval = 0) { invocations_ = newval; }

    unsigned int getAdditions() const { return additions_; }
    void resetAdditions(unsigned int newval = 0) { additions_ = newval; }

    operator ()(int n) {
        ++invocations_;
        counted_mystery &mystery = *this;

        if ( n == 0 || n == 1 ||  n ==  2) {
          return  n ;
        }
        // The code is about to perform two additions.
        additions_ += 2;
        return (mystery(n-1) + mystery(n-2) + mystery(n-3));
    }

   private:
    unsigned int count_, additions_;
};

int main(int argc, char *argv[])
{
    using ::std::cout;

    counted_mystery mystery;
    mystery(20);
    cout << "mystery was called " << mystery.getCount() << " times for n == 20\n";
    return 0;
};

用数学解决这个问题是一个有趣的问题，但可能也不是太有趣难的。我认为这将会呈指数级增长。

顺便说一句，不要使用 endl 除非那是您想要使用的。它非常慢，因为每当您使用它时它都会强制刷新缓冲区。使用'\n'。

Answer 4

另一种选择是使其成为类的方法，该方法允许使用成员变量而不是全局变量，同时保持 int Mystery(int) 接口干净。

Answer 5

声明两个不同的静态 int 变量来跟踪调用次数和加法运算的次数。

Answer 6

使用（并递增）全局变量。 http://www.cplusplus.com/doc/tutorial/variables/

我会请输入一个示例，但我的手受伤了。