C++ 함수 내부의 재귀 카운터

Question

현재 재귀 함수에 대한 할당 수행. 피보나치 프로그램을 요청 받았고 많은 문제없이 그렇게했습니다. 하지만 카운터를 만들 필요가 있습니다. 여기에 붙어 있습니다.

나는 어떻게 나는이에 카운터를 추가하려면이 기능

int fibonacci(int n) 
{ 
    if(n == 0) 
    { 
     //my fibonacci code 
    } 
    else if(n == 1) 
    { 
     //my fibonacci code 
    } 
    else 
    { 
     //my fibonacci code 
    } 
} 

있어? 카운터를 추가 할 때마다 잘못된 숫자가 반환됩니다.

편집 그냥 명확히하기 위해 제 기능은 피보나치 숫자를 생성하는 데 적합합니다. 필자는 함수 내부에 카운터를 추가하여 피보나치 수를 생성 할 때마다 호출되는 횟수를 볼 수 있습니다.

나는 이후 main 함수의 카운터를 초기화 한 다음 재귀에서 카운터를 증가시키는 방법을 시도했지만 번호가 정확한지는 알 수 없습니다. 예를 들어 피보나치 수가 610 인 경우 함수를 609 번 호출한다고 가정합니다. 맞습니까?

Answer 1

코드를 먼저 작성하십시오.

fib(0) = *deleted* 
fib(1) = *deleted* 
fib(n) = *deleted* 

귀하의 카운터 (당신은 여전히 ​​당신의 질문에 지정해야합니다) 일반적으로 함수 외부에 정의 된 전역 변수에 의해 구현 될 수 있지만 함수 내에서 변경 : 나는 당신에게 재귀 방정식을 제공합니다.

질문의 편집을 참조하십시오.

귀하의 전화 번호가 적합하지 않습니다. 당신의 작업을 더 이상 망치지 않기 위해서, 나는 Erlang에서 답을 줄 것이다. 그래서 당신은 C++ 작업에서 그것을 올바르게 얻는 방법을 알아 내야 만한다. :-)

-module(fib). 

-export([f/1]). 

%% returns a tupel { fibonacci value, number function calls } 
f(0) -> {0, 1}; 
f(1) -> {1, 1}; 
f(X) -> 
    {F1, C1} = f(X - 1), %% decompose tuple 
    {F2, C2} = f(X - 2), 
    {F1 + F2, C1 + C2}. %% return value 

쉘에서이를 실행하는 것은 준다 :

Eshell V5.10.1 (abort with ^G) 
1> c("q:/doc/erlang/fib", [{outdir, "q:/doc/erlang/"}]). 
{ok,fib} 
2> fib:f(0). 
{0,1} 
3> fib:f(1). 
{1,1} 
4> fib:f(2). 
{1,2} 
5> fib:f(3). 
{2,3} 
6> fib:f(4). 
{3,5} 
7> fib:f(5). 
{5,8} 
8> fib:f(6). 
{8,13} 
9> fib:f(7). 
{13,21} 
10> fib:f(15). 
{610,987} 
11> 

따라서 I 987 함수 F (15) = 610의 값으로 얻을 호출 얻는다.

여기 재미있는 비트는 피보나치 재귀 F에 대한 적절한 시작 조건에 대한 설명입니다 (상황은 미분 방정식과 비슷하며 다른 시작점은 다른 궤적/솔루션으로 나타납니다).

나는 @WhozCraig 올바르게 지적하면서 F 문제 (0) = 1, F (1) = 1, 그것이 있어야 얻었다 F (0) = 0, F (1) = 1

위의 Erlang 코드를 살펴보면 함수 호출의 수를 계산하는 계열의 계산은 피보나치 형식이기도하지만 (시리즈의 마지막 두 멤버를 추가하는 것), 그 중 하나는 시작이있는 것임을 알 수 있습니다 값 1과 1! :-)

Answer 2

카운터가 필요하지 않습니다. 귀하의 코드는 이미 거의 다 있습니다.

피보나치 수는 재귀를 통해 정의되므로 마지막 경우가 분명합니다. 다른 두 개는 재귀 관계를 닫을 때, 즉 마지막 경우가 무한 루프가되는 것을 피하기 위해서만 필요하다.

Answer 3

데모 용으로 계산해야한다고 생각 하시나요?

#include <iostream> 

// ... 

int fibonacci(int n, int &count) 
{ 
    ++count; 
    // other code ... 

    // and every time you call fibonacci recursively, 
    // simply pass in the same reference, like so: 
    if (...) { 
     fibonacci (new_n, count); 
    } 
} 

int main(int argc, char** argv) 
{ 
    // call it with an int variable initialized to 0: 
    int fibCnt = 0; 
    fibonacci(10, fibCnt); 
    std::cout << "Function was called "<<fibCnt<<" times"<<std::endl; 
}