一個遞歸函數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

另一個選擇是使這是一個允許使用成員變量而不是全局的類的方法，並且同時保持界面清潔。