C에서 재귀 기능 ++

Question

나는이 재귀 함수가있는 경우 : 나는 신비 (20)을 찾는 함께 일하고

int mystery(int n) { 

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

합니다.

미스테리 (20)를 계산하기 위해 함수를 계산할 때 수행되는 추가 연산 수와 미스테리 호출 수를 알 수있는 방법은 무엇입니까?

내가 좋아하는 몇 가지 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)를 계산하기 위해 얼마나 많은 수의 미스테리 호출이 발생했는지를 말하는 방식으로 많은 것을 믿지 않습니까?

도움 주셔서 감사합니다.

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

또 다른 옵션은 전역이 아닌 멤버 변수를 사용할 수있는 클래스의 메서드로 만드는 것인데 동시에 int mystery(int) 인터페이스를 깨끗하게 유지하는 것입니다.