一个递归函数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）工作。

如何计算函数的执行次数以及为了计算神秘程度（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语句在告诉我进行了多少次加法运算以及为了计算神秘程度（20）而有多少个mystery（）的调用方面做了很多工作？

感谢您的帮助！

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变量来跟踪调用的次数和加法操作的次数。

Answer 4

这是可以找出数学。但是如果你想用经验来衡量它，你可以在函数中使用一个静态计数器。这个逻辑很容易扩展到计数添加的数量。

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 5

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

我会输入一个例子，但我有一个手部受伤。

Answer 6

另一个选择是使这是一个允许使用成员变量而不是全局的类的方法，并且同时保持界面清洁。